没有递归的排列算法？爪哇岛

java permutation recursion sequence

2022-09-01 01:27:13

我想得到一个数字的所有组合，没有任何重复。比如 0.1.2、0.2.1、1.2.0、1.0.2、2.0.1、2.1.0。我试图找到一个简单的方案，但无法找到。我为它画了一个图形/树，这尖叫着使用递归。但是如果可能的话，我想在没有递归的情况下执行此操作。

任何人都可以帮我这样做吗？

答案 1

你应该使用这样一个事实，当你想要N个数字的所有排列时，有N个！可能性。因此，每个数字 x 从 1..N！对此类排列进行编码。下面是一个以迭代方式打印出刺痛的所有排列的示例。

private static void printPermutationsIterative(String string){
        int [] factorials = new int[string.length()+1];
        factorials[0] = 1;
        for (int i = 1; i<=string.length();i++) {
            factorials[i] = factorials[i-1] * i;
        }

        for (int i = 0; i < factorials[string.length()]; i++) {
            String onePermutation="";
            String temp = string;
            int positionCode = i;
            for (int position = string.length(); position > 0 ;position--){
                int selected = positionCode / factorials[position-1];
                onePermutation += temp.charAt(selected);
                positionCode = positionCode % factorials[position-1];
                temp = temp.substring(0,selected) + temp.substring(selected+1);
            }
            System.out.println(onePermutation);
        }
    }

答案 2

这是我一年前写的一个通用排列枚举器。它还可以产生“子排列”：

public class PermUtil <T> {
 private T[] arr;
 private int[] permSwappings;

 public PermUtil(T[] arr) {
  this(arr,arr.length);
 }

 public PermUtil(T[] arr, int permSize) {
  this.arr = arr.clone();
  this.permSwappings = new int[permSize];
  for(int i = 0;i < permSwappings.length;i++)
   permSwappings[i] = i;
 }

 public T[] next() {
  if (arr == null)
   return null;

  T[] res = Arrays.copyOf(arr, permSwappings.length);
  //Prepare next
  int i = permSwappings.length-1;
  while (i >= 0 && permSwappings[i] == arr.length - 1) {
   swap(i, permSwappings[i]); //Undo the swap represented by permSwappings[i]
   permSwappings[i] = i;
   i--;
  }

  if (i < 0)
   arr = null;
  else {   
   int prev = permSwappings[i];
   swap(i, prev);
   int next = prev + 1;
   permSwappings[i] = next;
   swap(i, next);
  }

  return res;
 }

 private void swap(int i, int j) {
  T tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
 }

}

我的算法背后的想法是，任何排列都可以表示为交换命令的唯一序列。例如，对于<A，B，C>，交换序列012将所有项目保留在原位，而122首先将索引0与索引1交换，然后将1与2交换，然后将2与2交换（即将其保留在原位）。这导致排列BCA。

这种表示与排列表示（即一对一关系）同构，并且在遍历排列空间时很容易“增量”。对于 4 个项目，它从 0123 （ABCD）开始，以 3333（DABC）结束。