Java: Looking for an algorithm for permutation

Question

Suppose I have an array.

String[] arr = {"a", "b", "c"};

I need to get all possible combinations, like this:

a
a b
a c
a b c
a c b
b
b a
b c
b a c
b c a
c
c a
c b
c a b
c b a

What fast algorithm should I use to get all combinations?

UPD

public static void permute(List<Integer> done, List<Integer> remaining {
    remaining.removeAll(Collections.<Integer>singletonList(null));
    done.removeAll(Collections.<Integer>singletonList(null));
    System.out.println(done);
    if (remaining.size() == 0) {
        return;
    }
    for (int i = 0; i < remaining.size(); i++) {
        Integer e = remaining.get(i);
        done.add(e);
        remaining.set(i, null);
        permute(done, remaining);
        remaining.add(e);
        done.set(i, null);
    }
}

Output

    []
    [1]
    [1, 2]
    [1, 2, 3]
    [1, 2, 3, 4]
    [2, 3, 4, 3]
    [2, 3, 4, 3, 4]
    [4, 3, 4, 3]
    [4, 3, 4, 3, 4]
    [4, 3, 4, 3, 4, 2]
    [3, 4, 3, 4, 2, 4]
    [3, 4, 3, 4, 2, 4, 2]
    [3, 4, 2, 4, 2, 3]
    [3, 4, 2, 4, 2, 3, 2]
    [3, 4, 2, 4, 2, 3, 2, 4]
    [4, 2, 4, 2, 3, 2, 4, 2]
    [4, 2, 4, 2, 3, 2, 4, 2, 4]
    [2, 3, 2, 4, 2, 4, 2]
    [2, 3, 2, 4, 2, 4, 2, 4]
    [2, 3, 2, 4, 2, 4, 2, 4, 3]
    [2, 3, 2, 4, 2, 4, 2, 4, 3, 1]
    [3, 2, 4, 2, 4, 2, 4, 3, 1, 3]
    [3, 2, 4, 2, 4, 2, 4, 3, 1, 3, 1]
    [4, 2, 4, 2, 4, 3, 1, 3, 1, 3]
    [4, 2, 4, 2, 4, 3, 1, 3, 1, 3, 1]
    [4, 2, 4, 2, 4, 3, 1, 3, 1, 3, 1, 4]
    [2, 4, 2, 4, 3, 1, 3, 1, 3, 1, 4, 1]
    [2, 4, 2, 4, 3, 1, 3, 1, 3, 1, 4, 1, 4]
    [2, 4, 3, 1, 3, 1, 3, 1, 4, 1, 4, 3]
    [2, 4, 3, 1, 3, 1, 3, 1, 4, 1, 4, 3, 4]
    [2, 4, 3, 1, 3, 1, 3, 1, 4, 1, 4, 3, 4, 1]
    [4, 3, 1, 3, 1, 3, 1, 4, 1, 4, 3, 4, 1, 4]
    [4, 3, 1, 3, 1, 3, 1, 4, 1, 4, 3, 4, 1, 4, 1]
    [3, 1, 3, 1, 4, 1, 4, 3, 4, 1, 4, 1, 3]
    [3, 1, 3, 1, 4, 1, 4, 3, 4, 1, 4, 1, 3, 1]
    [3, 1, 3, 1, 4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4]
    [3, 1, 3, 1, 4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4, 2]
    [1, 3, 1, 4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4]
    [1, 3, 1, 4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2]
    [1, 4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4]
    [1, 4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2]
    [1, 4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1]
    [4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2]
    [4, 1, 4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1]
    [4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4]
    [4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1]
    [4, 3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2]
    [3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1]
    [3, 4, 1, 4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2]
    [4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3]
    [4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2]
    [4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1]
    [4, 1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4]
    [1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1]
    [1, 3, 1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4]
    [1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1]
    [1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4]
    [1, 4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4, 2]
    [4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4, 2, 4]
    [4, 2, 4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4, 2, 4, 2]
    [4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4, 2, 4, 2, 1]
    [4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4, 2, 4, 2, 1, 2]
    [4, 2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4, 2, 4, 2, 1, 2, 4]
    [2, 4, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4, 2, 4, 2, 1, 2, 4, 2]
    [2, 4

, 2, 1, 2, 1, 4, 1, 2, 1, 2, 3, 2, 1, 4, 1, 4, 1, 4, 2, 4, 2, 1, 2, 4, 2, 4]

UPD3

I found some code and made redesign of it. So I got this:

public class Permutations {

    public static void main(String[] args) {
        Set<String> combos = new Permutations().combos("1", "2", "3", "4", "5");
        for (String combo : combos) {
            for (char e : combo.toCharArray()){
                System.out.printf("[%s]", e);
            }
            System.out.println();
        }
    }

    public Set<String> combos(String... input) {
        Set<String> set = new TreeSet<>();
        combos(input, set, input.length, new StringBuffer());
        return set;
    }

    private void combos(String[] input, Set<String> set, int len, StringBuffer buf) {
        if (len == 0) {
            String elem = unique(buf.toString());
            set.add(elem);
        } else {
            for (String t : input) {
                buf.append(t);
                combos(input, set, len - 1, buf);
                buf.deleteCharAt(buf.length() - 1);
            }
        }
    }

    private String unique(String input) {
        StringBuilder unique = new StringBuilder();
        for (int i = 0; i < input.length(); i++) {
            String si = input.substring(i, i + 1);
            if (unique.indexOf(si) == -1)
                unique.append(si);
        }
        return unique.toString();
    }

}

It works fine.

yeah, have you tried anything at all? if so, does it not work? — ultranaut, May 01 '15 at 17:11
It looks like you are asking for all ordered subsets, rather than permutations. You should use a recursive algorithm. — Nayuki, May 01 '15 at 17:52
try this http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/ — K139, May 01 '15 at 18:10
@K139: That won't work here. If you notice, `a,b` and `b,a` are both required. A normal permutation generation algorithm, with a minor tweak works. See my answer. — Programmer Person, May 01 '15 at 18:21
@barbara: The algorithm I gave works. You seems to have made a mistake in translating to Java. I have added the java code. — Programmer Person, May 05 '15 at 14:01

score 2 · Answer 1 · edited May 23 '17 at 12:02

I recently wrote Java class for generating permutations on any Comparable objects. Take a look at the code on my github page here, and few examples on how to use it.

Here is c/p of one of the examples:

public static void main(final String[] args) {
    Permutation<Integer> permutation = new Permutation<>(1, 2, 3);
    do {
        System.out.println(permutation);
    } while (permutation.nextPermutation());
}

This will print all permutations of 1, 2, 3 array.

From your question I understood that you need: All permutations of every subset of given set.

The part about getting all permutations of given set is done - using Permutation class. Now we need to know how can we get all subsets of given set. In the code below I have done that using bitmasks.

Plese check some of the links below on how to use bitmasks for generating all subsets of given set:

Here is what you will need:

public static void main(final String[] args) {
  List<String> list = Arrays.asList("a", "b", "c");
  int numberOfSubsets = 1 << list.size();

  for (int mask = 0; mask < numberOfSubsets; mask++) {
    List<String> subset = new ArrayList<>();
    int N = mask;

    for (int i = 0; i < list.size(); i++) {
      if (N % 2 == 1)
        subset.add(list.get(i));
      N /= 2;
    }

    Permutation<String> permutation = new Permutation<>(subset);
    do {
      System.out.println(permutation);
    } while (permutation.nextPermutation());
  }

}

We wrap every subset of given set around Permutation class and let it do the work.

Too complicated. The algorithm I gave is quite simple. This algorithm requires a dependency of another library (or copy of that code), and does not work for more than 32 integers. It has the advantage of being lazy though. — Programmer Person, May 05 '15 at 14:01

score 1 · Accepted Answer · edited May 23 '17 at 10:24

A normal permutation generation algorithm should work, all you need to do is tweak it to print prefixes of the permutation.

I recently gave an answer for permutations, but it is in python. Should be easy to convert to Java.

This is the code, with the tweak of prefix printing added:

def permute(done, remaining):

  print done  # Move this to the if below to print only full permutations.

  if not remaining:
    return

  sorted_rem = sorted(remaining)
  l = len(sorted_rem)

  for i in xrange(0, l):
    c = sorted_rem[i]

    # Move to c to done portion.
    done.append(c)
    remaining.remove(c)

    # Permute the remaining
    permute(done, remaining)

    # Put c back.
    remaining.append(c)
    # Remove from done.
    del done[-1]

def main():
  permute([], range(1,4))

if __name__ == "__main__":
  main()

And this is the output:

[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[1, 3, 2]
[2]
[2, 1]
[2, 1, 3]
[2, 3]
[2, 3, 1]
[3]
[3, 1]
[3, 1, 2]
[3, 2]
[3, 2, 1]

Here is the same algorithm in Java, which works for me, looks like your attempt has bugs (for example removing from done, setting to null instead of removing).

class Permutation {
  public static void print(ArrayList<Integer> array) {
    System.out.print("[");
    for (Integer elem: array) {
      System.out.print(elem.toString());
    }
    System.out.println("]");
  }

  public static void Permute(ArrayList<Integer> done,
                             ArrayList<Integer> remaining) {
    print(done);
    if (remaining.size() == 0) {
      return;
    }

    ArrayList<Integer> sorted = new ArrayList<Integer>(remaining);
    Collections.sort(sorted);
    for (int j = 0; j < remaining.size(); j++) {
      Integer c = sorted.get(j);
      remaining.remove(c);
      done.add(c);
      Permute(done, remaining);
      done.remove(c);
      remaining.add(0, c);
    }
  }

  public static void main(String[] args) {
    ArrayList<Integer> remaining =
      new ArrayList<Integer>(Arrays.asList(1,2,3,4));
    ArrayList<Integer> done = new ArrayList<Integer>();
    Permute(done, remaining);
  }
}

I added a py one instead of java, as I strongly suspect this might be homework. Besides, the py one was handily available... — Programmer Person, May 01 '15 at 18:18
@barbara: It is fine to ask about homework, IMO. Just didn't want to spoil your learning experience in case it was, i.e. I wasn't accusing you of anything. In fact, I am quite happy to see that you are in fact interacting with the people who answer your question! I see a lot of folks just ask a question and not bother to acknowledge the efforts put in by the other people who are trying to help them. — Programmer Person, May 01 '15 at 18:25
Note that the print method of Java assumes digits (made it that way to remove the pesky scrollbar). — Programmer Person, May 05 '15 at 14:06
Seems your solution doesn't work. Try to run it with `new ArrayList(Arrays.asList("A", "B", "C"));` It prints `[] [A] [AB] [ABC] [AC] [ACB] [C] [CA] [CAB] [CB] [CBA] [A] [AC] [ACB] [AB] [ABC]` — barbara, May 05 '15 at 21:13
@barbara: Looks like I put an older version. The line `Integer c = remaining.get(j)` must be `Integer c = sorted.get(j)`. Fixed. — Programmer Person, May 06 '15 at 01:03

Java: Looking for an algorithm for permutation

2 Answers2