algorithm - 获取整数列表的所有子列表的所有排列

Question

这个问题一直困扰着我。基本上，我有一个整数列表，例如

list = [1, 2, 3]

我想获得每个子集的所有可能排列。我知道网上存在类似的问题，但我找不到一个可以完成每个排列以及每个子集的问题。换句话说，我想要:

function(list) = 
[], [1], [2], [3],
[1, 2], [2, 1], [1, 3], [3,1], [2, 3], [3,2],
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]

我知道即使对于较小的输入列表大小，输出也会变得非常大。不幸的是，我就是不知道如何解决这样的问题。

谢谢!

Answer 1

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;

public class Test {

private static boolean[] used;
private static int[] a;

private static void f(int curCount,int subsetSize,ArrayDeque<Integer> perm){
   // System.out.println("in rec "+curCount+" "+subsetSize);
    if(curCount < subsetSize){
        for(int i=0;i<a.length;i++) {
            if (!used[i]) { // try to add i-th elem of array  as a next element of  permutation if it's not busy
                perm.add(a[i]);
                used[i] = true; //mark i-th element as used for  future recursion calls
                f(curCount + 1, subsetSize,perm); // curCount+1 because we added elem to perm. subsetSize is const and it's needed just for recursion exit condition
                used[i] = false; // "free" i-th element
                perm.removeLast();
            }
        }
    }
    else{ //some permutation of array subset with size=subsetSize generated
        for(Integer xx:perm) System.out.print(xx+" ");
        System.out.println();

    }
}

public static void main(String[] args){

  a = new int[]{1,2,3};
  used = new boolean[a.length];
  Arrays.fill(used, false);

  // second param is a subset size (all sizes from 1 to n)
  // first param is number of "collected" numbers, when collected numbers==required subset size (firstparam==second param) exit from recursion (from some particular call-chain)
  // third param is data structure for constructing permutation
  for(int i=1;i<=a.length;i++)f(0,i,new ArrayDeque<Integer>());

} //end of main

} //end of class

输出

1
2
3
1 2
1 3
2 1
2 3
3 1
3 2
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1