如何获得 Drools 中列表的所有可能组合？

Question

我有一个可变大小的列表，我想获得所有可能的组合。给定一个包含 {"A","B","C"} 的列表，我正在寻找以下输出（以任何顺序）：

A
AB
ABC
AC
B
BC
C

就像this js answer

我可以轻松得到预定义数字的所有排列，如下所示：

rule "Permutation of 3 List" extends "My List"
when
    $obj1: MyClass() from $myList
    $obj2: MyClass() from $myList
    $obj3: MyClass() from $myList
then
    List<MyClass> list = new ArrayList<MyClass>();
    list.add($obj1);
    list.add($obj2);
    list.add($obj3);
    insert(list);

结束

我不确定如何获得可变数字的排列，这可能对我需要组合没有帮助，但如果我可以获得 n 个大小为 k 的元素的所有排列，我可以运行大小为 1 到大小为 n 的 n 个元素的所有排列，然后从这些排列中取不同的值。但是，我还需要它相对高效，并且没有包含 20 个元素的列表会使服务器崩溃。

编辑：修复了 js 答案 link
编辑：删除添加的答案并发布为答案

Answer 1

假设您有一组 n 个元素 S = {"A", "B", "C", ... }。然后你可以构造一个大小为 n 的数组 X，其中 X[i] 表示第 i 个元素是否在排列中。

例如：S = {"A", "B", "C"} 以 X =[0,0,0]

开头

X = [0,0,1]代表"C"
X = [0,1,0] 表示 "B"
X = [0,1,1]代表"BC"
X = [1,0,0]代表"A"
X = [1,0,1]代表"AC"
X = [1,1,0]代表"AB"
X = [1,1,1]代表"ABC"

现在，对于 X 与一个以上“1”的每个组合，您可以使用当前算法找到所有排列。

即：对于 X = [1,1,0] 你将不得不输出 "AB" 和 "BA"，但是对于 X = [1,1,1] 你将不得不输出"ABC"、"ACB"、"BCA"、"BAC"、"CBA" 和 "CAB".

Answer 2

我想出了一个可能效率不高但有效的方法。

我做的第一件事是创建一个名为 Data 的简单 Java class 来包含字符串的初始列表（我不喜欢 JDK classes 作为事实）。

public class Data {
    private List<String> list = new ArrayList<>();

    public List<String> getList() {
        return list;
    }

    public void setList(List<String> list) {
        this.list = list;
    }    
}

然后，我使用一个中间事实在我的 DRL 中保存一个排列结果。

declare Permutation
    elements : List
end

然后，我创建了一个规则来为初始 data.

创建所有可能的排列（具有可变元素）

rule "Permutations"
when
    $d: Data()
    $obj1: String() from $d.getList() do[one]
    $obj2: String(this != $obj1) from $d.getList() do[two]
    $obj3: String((this != $obj1 && this != $obj2)) from $d.getList()
then
    List<String> list = Arrays.asList($obj1, $obj2, $obj3);
    insert(new Permutation(list));
then[one]
    List<String> list = Arrays.asList($obj1);
    insert(new Permutation(list));
then[two]
    List<String> list = Arrays.asList($obj1, $obj2);
    insert(new Permutation(list));
end

上面的规则使用 Conditional Named Consequences 来避免必须创建 3 个不同的规则。该规则还使用 this != $objX 类型的约束来避免重复元素的排列。然后每个 Permutation 作为一个独立的事实插入。

最后一步是从会话中删除 Permutations 具有相同元素的内容。为此，我使用了 List.containsAll() 方法。

rule "Trim duplicated Permutations"
when
    $p1: Permutation()
    $p2: Permutation(
        this != $p1, 
        elements.size == $p1.elements.size,
        elements.containsAll($p1.elements)
    )
then
    retract($p2);
end

就是这样！为了从您的 Java 应用程序中获取会话中剩余的排列，我使用了一个查询：

query getPermutations()
    Permutation($p: elements)
end

我用来测试的 Java 代码是：

List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");

        Data data = new Data();
        data.setList(list);

        ksession.insert(data);
        ksession.fireAllRules();

        QueryResults results = ksession.getQueryResults("getPermutations");
        for (QueryResultsRow row : results) {
            List<String> permutation = (List<String>)row.get("$p");

            String m = "Permutation: {"+permutation.stream().collect(Collectors.joining(","))+"}";
            System.out.println(m);
        }

希望对您有所帮助，

Answer 3

我想出了一种方法来获取 Drools 中 n 项列表的所有组合，但我不会说这是 Drools 的方式。这是我的规则，它获取我的列表并从列表中获取所有组合：

    rule "Combinations of List" extends "My List"
salience 100
when
then
    //bit shift left j places, equivalent to Math.pow(2,j);
    int max = 1 << $myList.size();
    for(int i = 1; i < max; i++){
        insert(new ComboNumber(i));
    }
end

这个想法来自@FlyingPumba 评论和 dba answer here

int 只是位，对于所有组合，我需要位 0b001-0b111（1-7 的二进制）以及它们之间的所有组合。然后 001 是 "A"，111 是 "ABC"，101 是 "AC"，等等......我从 (2^n)-1 得到它，在这种情况下是 (2^3)- 1，即 7，然后遍历所有值 [1,2,3,4,5,6,7]，为每个值插入一个新的 ComboNumber 到工作内存。

然后对于这些 ComboNumber 中的每一个，我需要从该数字的位构造 MyClass 的组合：

rule "Construct Combination From Bits" extends "My List"
salience 100
when
    $list: List()
    ComboNumber($number: number) from $list
then
    List comboList = new ArrayList();
    for (int bit = 0; bit < $myList.size(); bit++)
{
    //if current bit position is flipped on
    //bitshift right of 0b001101 2 places is 0b0011
    //logical AND of (0b0011 and 0b0001) = 0b0001 (or decimal 1)
    if((($number >> bit) & 1) == 1){
        //get obj associated with bit position
        comboList.add($myList.get(bit));
    }
}
    insert(new Combinations(comboList));
end

这种方式可行，但...在性能上不是很好。毕竟是 O(2^n)。我相信获得所有排列是 O(n^n)，所以它可能更糟。包含 17 个或更少项目的列表是亚秒级的，但 20 个需要 23 秒（即 1,048,576 种组合）。

如果你能想出更好的性能方法，请告诉我。运行它直接在 C# 中（在我的同一台机器上）大约快 23 倍（单线程）或并行快 46 倍，每秒成功迭代约 2m 组合。

如何获得 Drools 中列表的所有可能组合？

How can I get all possible combinations of a list in Drools?

algorithm

drools