Print permutations of two given sets

Question

Given is a set M with some elements, e.g. M={a, b} and another set F with specific numbers representing the quantity in the permutations of M. e.g. F={3, 1}, so the permutations are: P={(a, a, a, b), (a, a, b, a), (a, b, a, a), (b, a, a, a)} for this example.

I want to print those but after fiddling around with recursion I still can't get it to work. My current code is like:

void printPermutations(Map<Integer, String> m, List<Integer> f, List<Integer> cf, int size, int depth, int index, int innerindex, List<String> toPrint)
{
    if(depth == size)
    {
        System.out.println("");
        for(String a : toPrint)
            System.out.print(a + " ");
        System.out.println("");
    }
    else
    {
        for(int i = index + 1; i < m.size(); ++i)
        {   
            if(f.get(innerindex).compareTo(Integer.valueOf(1)) < 0)
                ++innerindex;

            toPrint.add(m.get(innerindex));

            f.set(innerindex, f.get(innerindex) - Integer.valueOf(1));
            printPermutations(m, f, f, size, depth + 1, i, innerindex, toPrint);
            f.set(innerindex, f.get(innerindex) + Integer.valueOf(1));

            toPrint.remove(m.get(innerindex));

            if(f.get(innerindex).compareTo(cf.get(innerindex)) == 0 && innerindex > 0)
                --innerindex;
        }
    }
}

//call
//asume some cool elements in f and mAsSet
//    f.size() == mAsSet.size()

List<String> toPrint = new ArrayList<String>();
Map<Integer, String> m = new HashMap<Integer, String>(mAsSet.size());
int counter = 0;
for(String a : m)
    m.put(Integer.valueOf(counter++), a);
int size = 0;
for(Integer i : f)
    size += i;
printPermutations(m, f, f, size, 0, -1, 0, toPrint);

I don't really see whats wrong here, it prints exactly nothing. Of course I debugged this, but I really do not have any other idea to kindof archieve what I want.

Why change your working code to pseudocode? Add the executable code so people can fiddle around with it if they want to. — Jeroen Vannevel, Nov 12 '14 at 21:26
@JeroenVannevel: Sorry, I just didn't want any offtopic about my Java-stuff — NaCl, Nov 12 '14 at 21:37
Perhaps this topic can help you. You will need to apply the logic to your needs. http://stackoverflow.com/questions/4240080/generating-all-permutations-of-a-given-string — Rami Del Toro, Nov 12 '14 at 21:43
I mean of course I could just make a big list with all permutations and remove those which are doubled, but thats not that performance you might want, isnt it? — NaCl, Nov 12 '14 at 21:55

score 1 · Accepted Answer · answered Nov 12 '14 at 22:40

Take a look how the big boys are handling permutations. If the code you're working on can include 3rd party libraries than use guava. That would result with something like:

final ImmutableList<String> m = ImmutableList.of("a", "b");
final ImmutableList<Integer> f = ImmutableList.of(3, 1);

final ImmutableList<String> values = FluentIterable.from(m).
  transformAndConcat(new Function<String, Iterable<String>>() {

    int c = 0;

    public Iterable<String> apply(String input) {
        return Collections.nCopies(f.get(c++), input);
    }
}).toList();

final ImmutableSet<List<String>> permutations = ImmutableSet.copyOf(Collections2.permutations(values));
System.out.println(Joiner.on("\n").join(permutations));

The Collections2.permutations will generate duplicate outputs (i.e. [a, a, a, b] will occur multiple times, but because permutation is implemented as Iterator no extra memory is used as the resulting ImmutableSet contains only single value. The iteration runs values! (factorial) times though.

Thats exactly not that what I wanted. No doubled `(a, a, a, b)` — NaCl, Nov 12 '14 at 22:48
The Collections2.permutations will output (a, a, a, b) multiple times, but ImmutableSet.copyOf prevents that from happening in the permutations Set. — Zoran Regvart, Nov 12 '14 at 22:53

Print permutations of two given sets

1 Answers1