没有递归的置换算法？ Java的 [英] Permutation algorithm without recursion? Java

问题描述

我想得到一个数字的所有组合而不重复。
如0.1.2,0.2.1,1.2.0,1.0.2,2.0.1,2.1.0。
我试图找到一个简单的方案，但不能。我为它绘制了一个图形/树，这尖叫使用递归。
但是如果可能的话，我想在没有递归的情况下这样做。

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?

推荐答案

这是我一年前写的一个通用排列调查员。它还可以产生子排列：

Here is a generic permutation enumerator I wrote a year ago. It can also produce "sub-permutations":

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通过交换索引为1的索引0，然后用2交换1，然后用2交换2（即离开它）到位）。这导致置换BCA。

The idea behind my algorithm is that any permutation can be expressed as a unique sequence of swap commands. For example, for <A,B,C>, the swap sequence 012 leaves all items in place, while 122 starts by swapping index 0 with index 1, then swaps 1 with 2, and then swaps 2 with 2 (i.e. leaves it in place). This results in the permutation BCA.

此表示与置换表示同构（即一对一关系），并且在遍历排列空间时非常容易递增它。对于4个项目，它从0123（ABCD）开始，到3333（DABC）结束。

This representation is isomorphic to the permutation representation (i.e. one to one relationship), and it is very easy to "increment" it when traversing the permutations space. For 4 items, it starts from 0123 (ABCD) and ends with 3333(DABC).

这篇关于没有递归的置换算法？ Java的的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！