Constraining all combinations of an array-list

Question

I know similar questions have been asked before but I have found the answers confusing. I am trying to make a program that will find every combination of an array-list with no repetitions and only of the maximum size. If the list has 4 items it should print out only the combinations with all 4 items present. This is what I have so far:

public main(){
    UI.initialise();
    UI.addButton("Test", this::testCreate);
    UI.addButton("Quit", UI::quit);
}

public void createCombinations(ArrayList<String> list, String s, int depth) {
    if (depth == 0) {
        return;
    }

    depth --;

    for (int i = 0; i < list.size(); i++) {
        if (this.constrain(s + "_" + list.get(i), list.size())) {
            UI.println(s + "_" + list.get(i));
        }
        createCombinations(list, s + "_" + list.get(i), depth);
    }
}

public void testCreate() {
    ArrayList<String> n = new ArrayList<String>();
    n.add("A"); n.add("B"); n.add("C"); n.add("D");
    this.createCombinations(n , "", n.size());
}

public boolean constrain(String s, int size) {
    // Constrain to only the maximum length
    if ((s.length() != size*2)) {
        return false;
    }

    // Constrain to only combinations without repeats
    Scanner scan = new Scanner(s).useDelimiter("_");
    ArrayList<String> usedTokens = new ArrayList<String>();
    String token;

    while (scan.hasNext()) {
        token = scan.next();
        if (usedTokens.contains(token)) {
            return false;
        } else {
            usedTokens.add(token);
        }
    }

    // If we fully iterate over the loop then there are no repitions
    return true;
}

public static void main(String[] args){
    main obj = new main();
}

This prints out the following which is correct:

_A_B_C_D
_A_B_D_C
_A_C_B_D
_A_C_D_B
_A_D_B_C
_A_D_C_B
_B_A_C_D
_B_A_D_C
_B_C_A_D
_B_C_D_A
_B_D_A_C
_B_D_C_A
_C_A_B_D
_C_A_D_B
_C_B_A_D
_C_B_D_A
_C_D_A_B
_C_D_B_A
_D_A_B_C
_D_A_C_B
_D_B_A_C
_D_B_C_A
_D_C_A_B
_D_C_B_A

This works for small lists but is very inefficient for larger ones. I am aware that what I have done is completely wrong but I want to learn the correct way. Any help is really appreciated. Thanks in advance.

P.S. This is not homework, just for interest although I am a new CS student (if it wasn't obvious).

if its working whats the issue or is this more of a code review/ looking for improvement? — dave, Jul 01 '18 at 12:41
String manipulation is generally expensive when it comes to something like permutations at higher levels. They are too heavy when the input gets long. On the other hand, integers play fairly well in these scenarios. My take on this is, treat all elements as (alphabet letters in this case) numeric values and do bitwise operations to shift values around to get a single combination. Try something like C or python, I think they are better suited for something like this. — Infamous, Jul 01 '18 at 12:48
Is there anything I can do to the for loop to make it only iterate over the length I want (the length of the list)? — Ben, Jul 01 '18 at 13:11
Check [this](https://stackoverflow.com/a/2710716/6746785) which I think is a duplicate. — gthanop, Jul 01 '18 at 13:22

score 0 · Accepted Answer · answered Jul 01 '18 at 13:42

Implementing Heap's algorithm in Java:

import java.util.Arrays;

public class Main {
    public static void swap(final Object[] array, final int index1, final int index2) {
        final Object tmp = array[index1];
        array[index1] = array[index2];
        array[index2] = tmp;
    }

    public static void printPermutations_HeapsAlgorithm(final int n, final Object[] array) {
        final int[] c = new int[n];

        for (int i = 0; i < c.length; ++i)
            c[i] = 0;

        System.out.println(Arrays.toString(array)); //Consume first permutation.

        int i=0;

        while (i < n) {
            if (c[i] < i) {
                if ((i & 1) == 0)
                    swap(array, 0, i);
                else
                    swap(array, c[i], i);

                System.out.println(Arrays.toString(array)); //Consume permutation.

                ++c[i];
                i=0;
            }
            else
                c[i++] = 0;
        }
    }

    public static void main(final String[] args) {
        printPermutations_HeapsAlgorithm(4, new Character[]{'A', 'B', 'C', 'D'});
    }
}

Possible duplicate of this.

Thank you! Exactly what I was looking for. – Ben Jul 01 '18 at 13:57 — Ben, Jul 01 '18 at 13:57

Constraining all combinations of an array-list

1 Answers1