I would like to get all combination of a number without any repetition. Like 0.1.2, 0.2.1, 1.2.0, 1.0.2, 2.0.1, 2.1.0. I tried to find an easy scheme, but couldn't. I drew a graph/tree for it and this screams to use recursion. But I would like to do this without recursion, if this is possible.
Can anyone please help me to do that?
It is easy to write the recursive permutation, but it requires exporting the permutations from deeply nested loops. (That is an interesting exercise.) I needed a version that permuted strings for anagrams. I wrote a version that implements Iterable<String> so it can be used in foreach loops. It can easily be adapted to other types such as int[] or even a generic type <T[]> by changing the constructor and the type of attribute 'array'.
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* An implicit immutable collection of all permutations of a string with an
* iterator over the permutations.<p> implements Iterable<String>
* @see #StringPermutation(String)
*/
public class StringPermutation implements Iterable<String> {
// could implement Collection<String> but it's immutable, so most methods are essentially vacuous
protected final String string;
/**
* Creates an implicit Iterable collection of all permutations of a string
* @param string String to be permuted
* @see Iterable
* @see #iterator
*/
public StringPermutation(String string) {
this.string = string;
}
/**
* Constructs and sequentially returns the permutation values
*/
@Override
public Iterator<String> iterator() {
return new Iterator<String>() {
char[] array = string.toCharArray();
int length = string.length();
int[] index = (length == 0) ? null : new int[length];
@Override
public boolean hasNext() {
return index != null;
}
@Override
public String next() {
if (index == null) throw new NoSuchElementException();
for (int i = 1; i < length; ++i) {
char swap = array[i];
System.arraycopy(array, Here is the generic and iterative permutation, kpermutation and combination generator classes that I wrote based on the implementations here and here. My classes use those as inner classes. They also implement Iterable Interface to be foreachable.
List<String> objects = new ArrayList<String>();
objects.add("A");
objects.add("B");
objects.add("C");
Permutations<String> permutations = new Permutations<String>(objects);
for (List<String> permutation : permutations) {
System.out.println(permutation);
}
Combinations<String> combinations = new Combinations<String>(objects, 2);
for (List<String> combination : combinations) {
System.out.println(combination);
}
KPermutations<String> kPermutations = new KPermutations<String>(objects, 2);
for (List<String> kPermutation : kPermutations) {
System.out.println(kPermutation);
}
The Combinations class:
public class Combinations<T> implements Iterable<List<T>> {
CombinationGenerator cGenerator;
T[] elements;
int[] indices;
public Combinations(List<T> list, int n) {
cGenerator = new CombinationGenerator(list.size(), n);
elements = (T[]) list.toArray();
}
public Iterator<List<T>> iterator() {
return new Iterator<List<T>>() {
int pos = 0;
public boolean hasNext() {
return cGenerator.hasMore();
}
public List<T> next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
indices = cGenerator.getNext();
List<T> combination = new ArrayList<T>();