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

Question

I have a list of variable size that I'd like to get all possible combinations for. Given a List with {"A","B","C"} I'm looking for the following output (in any order):

A
AB
ABC
AC
B
BC
C

just like this js answer

I can get all permutations easily for predefined number, as shown below:

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);

end

I'm not sure how I can get permutations for a variable number, and it may not help as I need the combinations, but if I could get all permutations for n elements of size k, I could run all permutations for n elements size 1 up to size n, then take the distinct values from those permutations. I would also need this to be relatively efficient, however, and not have a list with 20 elements crash the server.

edit: fixed js answer link
edit: removed added answer and posted as answer

Answer 1

I came up with a way to get all combinations of a list of n items in Drools, but I wouldn't say it's the Drools way. Here's my rule that takes my list and gets all combinations from the list:

    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

The idea was drawn from the @FlyingPumba comment and the dba answer here

An int is just bits and for all combinations I need bits 0b001-0b111 (which is binary for 1-7) and all the combinations in between. Then 001 is "A", 111 is "ABC", 101 is "AC", etc... I get that from (2^n)-1, in this case (2^3)-1, which is 7, then iterate through all values [1,2,3,4,5,6,7], inserting a new ComboNumber to working memory for each.

Then for each of those ComboNumber(s) I need to construct the combination of MyClass from the bits of that number:

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

This way works, but...not so great on performance. It is O(2^n) after all. I believe getting all permutations is O(n^n), so it could be a lot worse. A list with 17 or fewer items is sub-second, but 20 takes 23 seconds (which IS 1,048,576 combinations).

If you can think of a way to get better performance for it, please let me know. Running it directly in C# (on my same machine) is about 23x faster (single threaded) or 46x faster in parallel, successfully iterating about 2m combos per second.

Answer 2

I came up with a way that may not be efficient but works.

First thing I did was to create a simple Java class called Data to contain the initial list of Strings (I don't like JDK classes as facts).

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

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

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

Then, I used an intermediate fact to hold a permutation result in my DRL.

declare Permutation
    elements : List
end

Then, I created a rule to create all the possible permutations (with variable elements) for an initial 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

The rule above uses Conditional Named Consequences to avoid having to create 3 different rules. The rule also uses constraints of the type this != $objX to avoid permutations with duplicated elements. Each Permutation is then inserted as an independent fact.

The last step is to remove from the session Permutations with the same elements. I used List.containsAll() method for this.

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

And that's it! In order to get the remaining Permutations in my session from your Java app, I used a query:

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

The Java code I used to test this was:

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);
        }

Hope it helps,

Answer 3

Let's say you have a set of n elements S = {"A", "B", "C", ... }. Then you can construct an array X of size n where X[i] says if the i-th element is in the permutation.

For example: S = {"A", "B", "C"} and start with X =[0,0,0]

• X = [0,0,1] represents "C"
• X = [0,1,0] represents "B"
• X = [0,1,1] represents "BC"
• X = [1,0,0] represents "A"
• X = [1,0,1] represents "AC"
• X = [1,1,0] represents "AB"
• X = [1,1,1] represents "ABC"

Now for each combination of X with more than one "1" you can use your current algorithm to find all permutations.

I.e: for X = [1,1,0] you will have to output "AB" and "BA", but for X = [1,1,1] you will have to output "ABC", "ACB", "BCA", "BAC", "CBA" and "CAB".