Java: finding a permutation algorithm
Suppose I have an array.
String[] arr = {"a", "b", "c"};
I need to get all possible combinations, for example:
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 is the fastest algorithm to 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 the code and refactored 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 great.
source to share
The algorithm for generating normal permutations should work, all you have to do is configure it to print permutation prefixes.
I recently gave an answer for permutations , but it's in python. Should be easy to convert to Java.
This is the code, with the addition of the print prefix settings:
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 result:
[]
[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 that works for me, it looks like your attempt has errors (like deleting from done, setting to null instead of deleting).
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);
}
}
source to share
I recently wrote a Java class to generate permutations for any object Comparable
. Take a look at the code on my github page here and some examples on how to use it.
Here's the c / p of one example:
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 the array 1, 2, 3
.
From your question, I figured out what you need: All permutations for each subset of a given set.
The part about getting all permutations of a given set is done using a class Permutation
. Now we need to know how we can get all subsets of a given set. In the code below, I have done it using bitmasks.
Plese will check out some of the links below on how to use bitmasks to generate all subsets of a given set:
- Printing all possible subsets of a list
- http://www.ugrad.cs.ubc.ca/~cs490/sec202/notes/intro/bitmask.pdf
Here's what you 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 up each subset of the given set around the class Permutation
and let it do the work.
source to share