java - 打印两个给定集合的排列

Question

给定的是一个包含一些元素的集合 M，例如M={a, b} 和另一组 F，其中特定数字表示 M 排列中的数量。例如F={3, 1}，所以排列是:P={(a, a, a, b), (a, a, b, a), (a, b , a, a), (b, a, a, a)} 这个例子。

我想打印那些，但在摆弄递归之后我仍然无法让它工作。我当前的代码是这样的:

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);

我真的看不出这里有什么问题，它什么都不打印。当然，我对此进行了调试，但我真的没有任何其他想法来实现我想要的东西。

Answer 1

看看big boys are handling permutations如何.如果您正在处理的代码可以包含第三方库而不是使用 guava .这将导致类似的结果:

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));

Collections2.permutations 将生成重复的输出(即 [a, a, a, b] 将出现多次，但是因为置换是作为 Iterator 实现的，所以不会使用额外的内存，因为生成的 ImmutableSet 仅包含单个值。迭代虽然运行值!(阶乘)次。