我希望能够获取一个数字的所有组合，且没有重复。 像0.1.2、0.2.1、1.2.0、1.0.2、2.0.1、2.1.0这样。 我试图找到一个简单的方法，但是失败了。我画了一张图/树来解决它，这正呼唤着使用递归。 但如果可能的话，我想不用递归来做这个。
请问有人可以帮我吗？
不使用递归的排列算法？Java
43
- Andreas Hornig
10
5递归是解决这个问题的自然方法。为什么你想在不适用递归的情况下解决它呢？任何明智的“非递归”解决方案最终都会使用单独的堆栈来模拟递归。 - Greg Hewgill
3@Greg 可读性呢？很多人发现递归难以理解 - 不使用递归也许会使意图更加明确？ - Robben_Ford_Fan_boy
4需要支持这种说法，需要一个更易读的非递归解决方案的例子。 - Greg Hewgill
1我怀疑可以找到一些公式，可以将排列元素的值作为计数的函数来给出。类似于f(seq,len,place)=(seq!place)%len..（当然不是这个，我还没有破解）。但我可以看出，能够以公式的形式表达唯一排列模式的细节可能非常有用。 - strainer
一个非递归的解决方案是贝尔置换算法，就像我在答案中描述的那样。 - Anders
显示剩余5条评论
13个回答
24
你应该利用这样一个事实，当你想要得到N个数字的所有排列时，有N!种可能性。因此，1..N!中的每个数字x都编码了这样一个排列。以下是一个示例，迭代地打印出字符串的所有排列。
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);
}
}
- Filip Nguyen
3
1如果我在答案中使用这个算法（转换为Javascript），我需要归功于你吗？还是你使用了其他来源？ - m69 ''snarky and unwelcoming''
你可以归功于我。 - Filip Nguyen
5请参考 https://en.wikipedia.org/wiki/Factorial_number_system 中关于排列组合的部分，以了解这段代码的作用。 - morpheus
19
以下是我一年前编写的通用排列枚举器。它还可以生成“子排列”：
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）结束。
- Eyal Schneider
12
一般来说，任何递归算法都可以通过使用栈或队列数据结构将其转换为迭代算法。
对于这个特定问题，更有启示性的方法是查看C++ STL算法std::next_permutation。根据wordaligned.org上Thomas Guest的说法，基本实现如下:
template<typename Iter>
bool next_permutation(Iter first, Iter last)
{
if (first == last)
return false;
Iter i = first;
++i;
if (i == last)
return false;
i = last;
--i;
for(;;)
{
Iter ii = i;
--i;
if (*i < *ii)
{
Iter j = last;
while (!(*i < *--j))
{}
std::iter_swap(i, j);
std::reverse(ii, last);
return true;
}
if (i == first)
{
std::reverse(first, last);
return false;
}
}
}
需要注意的是，这段代码不使用递归，并且相对容易转换成其他类C语言，例如Java。你可能需要阅读关于 std::iter_swap、std::reverse 和 双向迭代器（在此代码中表示为Iter）的知识。
- bobbymcr
2
3描述在这里：http://en.wikipedia.org/wiki/Permutation#Systematic_generation_of_all_permutations - leonbloy
11
编写递归排列很容易，但需要从深层嵌套的循环中导出排列。(这是一个有趣的练习。)我需要一个可以为字谜重新排列字符串的版本。我编写了一个实现Iterable<String>的版本，因此它可以用于foreach循环。通过更改构造函数和属性“array”的类型，它可以轻松地适应其他类型，如int[]或甚至是泛型类型<T[]>。
import java.util.Iterator;
import java.util.NoSuchElementException;
/**
* An implicit immutable collection of all permutations of a string with an
* iterator over the permutations.<p> implements Iterable<String>
* @see #StringPermutation(String)
*/
public class StringPermutation implements Iterable<String> {
// could implement Collection<String> but it's immutable, so most methods are essentially vacuous
protected final String string;
/**
* Creates an implicit Iterable collection of all permutations of a string
* @param string String to be permuted
* @see Iterable
* @see #iterator
*/
public StringPermutation(String string) {
this.string = string;
}
/**
* Constructs and sequentially returns the permutation values
*/
@Override
public Iterator<String> iterator() {
return new Iterator<String>() {
char[] array = string.toCharArray();
int length = string.length();
int[] index = (length == 0) ? null : new int[length];
@Override
public boolean hasNext() {
return index != null;
}
@Override
public String next() {
if (index == null) throw new NoSuchElementException();
for (int i = 1; i < length; ++i) {
char swap = array[i];
System.arraycopy(array, 0, array, 1, i);
array[0] = swap;
for (int j = 1 ; j < i; ++j) {
index[j] = 0;
}
if (++index[i] <= i) {
return new String(array);
}
index[i] = 0;
}
index = null;
return new String(array);
}
@Override
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
- dickf
7
迄今为止我看到的大多数例子要么太复杂，只使用字符串或者使用交换，所以我想做一个迭代的、直观的、通用的且不使用交换的例子。
public static <T> List<List<T>> permutations(List<T> es){
List<List<T>> permutations = new ArrayList<List<T>>();
if(es.isEmpty()){
return permutations;
}
// We add the first element
permutations.add(new ArrayList<T>(Arrays.asList(es.get(0))));
// Then, for all elements e in es (except from the first)
for (int i = 1, len = es.size(); i < len; i++) {
T e = es.get(i);
// We take remove each list l from 'permutations'
for (int j = permutations.size() - 1; j >= 0; j--) {
List<T> l = permutations.remove(j);
// And adds a copy of l, with e inserted at index k for each position k in l
for (int k = l.size(); k >= 0; k--) {
ArrayList<T> ts2 = new ArrayList<>(l);
ts2.add(k, e);
permutations.add(ts2);
}
}
}
return permutations;
}
例子：我们想要 [a,b,c] 的所有排列组合。
我们添加 a，得到 [a] // 剩下 [b,c]
我们从列表中取出 a 并添加 [a,b] 和 [b,a] // 剩下 [c]
我们移除 [b,a]，插入 [b,a,c]、[b,c,a] 和 [c,b,a]，然后我们移除 [a,b]，插入 [a,b,c]、[a,c,b] 和 [c,a,b]
- Mattias F
5
这里是我根据这里和这里的实现编写的通用和迭代排列、k排列和组合生成器类。我的类使用它们作为内部类，并实现了可迭代接口以便于foreach循环。
List<String> objects = new ArrayList<String>();
objects.add("A");
objects.add("B");
objects.add("C");
Permutations<String> permutations = new Permutations<String>(objects);
for (List<String> permutation : permutations) {
System.out.println(permutation);
}
Combinations<String> combinations = new Combinations<String>(objects, 2);
for (List<String> combination : combinations) {
System.out.println(combination);
}
KPermutations<String> kPermutations = new KPermutations<String>(objects, 2);
for (List<String> kPermutation : kPermutations) {
System.out.println(kPermutation);
}
组合类（Combinations class）：
public class Combinations<T> implements Iterable<List<T>> {
CombinationGenerator cGenerator;
T[] elements;
int[] indices;
public Combinations(List<T> list, int n) {
cGenerator = new CombinationGenerator(list.size(), n);
elements = (T[]) list.toArray();
}
public Iterator<List<T>> iterator() {
return new Iterator<List<T>>() {
int pos = 0;
public boolean hasNext() {
return cGenerator.hasMore();
}
public List<T> next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
indices = cGenerator.getNext();
List<T> combination = new ArrayList<T>();
for (int i = 0; i < indices.length; i++) {
combination.add(elements[indices[i]]);
}
return combination;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
private final class CombinationGenerator {
private int[] a;
private int n;
private int r;
private BigInteger numLeft;
private BigInteger total;
//------------
// Constructor
//------------
public CombinationGenerator(int n, int r) {
if (n < 1) {
throw new IllegalArgumentException("Set must have at least one element");
}
if (r > n) {
throw new IllegalArgumentException("Subset length can not be greater than set length");
}
this.n = n;
this.r = r;
a = new int[r];
BigInteger nFact = getFactorial(n);
BigInteger rFact = getFactorial(r);
BigInteger nminusrFact = getFactorial(n - r);
total = nFact.divide(rFact.multiply(nminusrFact));
reset();
}
//------
// Reset
//------
public void reset() {
for (int i = 0; i < a.length; i++) {
a[i] = i;
}
numLeft = new BigInteger(total.toString());
}
//------------------------------------------------
// Return number of combinations not yet generated
//------------------------------------------------
public BigInteger getNumLeft() {
return numLeft;
}
//-----------------------------
// Are there more combinations?
//-----------------------------
public boolean hasMore() {
return numLeft.compareTo(BigInteger.ZERO) == 1;
}
//------------------------------------
// Return total number of combinations
//------------------------------------
public BigInteger getTotal() {
return total;
}
//------------------
// Compute factorial
//------------------
private BigInteger getFactorial(int n) {
BigInteger fact = BigInteger.ONE;
for (int i = n; i > 1; i--) {
fact = fact.multiply(new BigInteger(Integer.toString(i)));
}
return fact;
}
//--------------------------------------------------------
// Generate next combination (algorithm from Rosen p. 286)
//--------------------------------------------------------
public int[] getNext() {
if (numLeft.equals(total)) {
numLeft = numLeft.subtract(BigInteger.ONE);
return a;
}
int i = r - 1;
while (a[i] == n - r + i) {
i--;
}
a[i] = a[i] + 1;
for (int j = i + 1; j < r; j++) {
a[j] = a[i] + j - i;
}
numLeft = numLeft.subtract(BigInteger.ONE);
return a;
}
}
}
排列类：
public class Permutations<T> implements Iterable<List<T>> {
PermutationGenerator pGenerator;
T[] elements;
int[] indices;
public Permutations(List<T> list) {
pGenerator = new PermutationGenerator(list.size());
elements = (T[]) list.toArray();
}
public Iterator<List<T>> iterator() {
return new Iterator<List<T>>() {
int pos = 0;
public boolean hasNext() {
return pGenerator.hasMore();
}
public List<T> next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
indices = pGenerator.getNext();
List<T> permutation = new ArrayList<T>();
for (int i = 0; i < indices.length; i++) {
permutation.add(elements[indices[i]]);
}
return permutation;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
private final class PermutationGenerator {
private int[] a;
private BigInteger numLeft;
private BigInteger total;
//-----------------------------------------------------------
// Constructor. WARNING: Don't make n too large.
// Recall that the number of permutations is n!
// which can be very large, even when n is as small as 20 --
// 20! = 2,432,902,008,176,640,000 and
// 21! is too big to fit into a Java long, which is
// why we use BigInteger instead.
//----------------------------------------------------------
public PermutationGenerator(int n) {
if (n < 1) {
throw new IllegalArgumentException("Set must have at least one element");
}
a = new int[n];
total = getFactorial(n);
reset();
}
//------
// Reset
//------
public void reset() {
for (int i = 0; i < a.length; i++) {
a[i] = i;
}
numLeft = new BigInteger(total.toString());
}
//------------------------------------------------
// Return number of permutations not yet generated
//------------------------------------------------
public BigInteger getNumLeft() {
return numLeft;
}
//------------------------------------
// Return total number of permutations
//------------------------------------
public BigInteger getTotal() {
return total;
}
//-----------------------------
// Are there more permutations?
//-----------------------------
public boolean hasMore() {
return numLeft.compareTo(BigInteger.ZERO) == 1;
}
//------------------
// Compute factorial
//------------------
private BigInteger getFactorial(int n) {
BigInteger fact = BigInteger.ONE;
for (int i = n; i > 1; i--) {
fact = fact.multiply(new BigInteger(Integer.toString(i)));
}
return fact;
}
//--------------------------------------------------------
// Generate next permutation (algorithm from Rosen p. 284)
//--------------------------------------------------------
public int[] getNext() {
if (numLeft.equals(total)) {
numLeft = numLeft.subtract(BigInteger.ONE);
return a;
}
int temp;
// Find largest index j with a[j] < a[j+1]
int j = a.length - 2;
while (a[j] > a[j + 1]) {
j--;
}
// Find index k such that a[k] is smallest integer
// greater than a[j] to the right of a[j]
int k = a.length - 1;
while (a[j] > a[k]) {
k--;
}
// Interchange a[j] and a[k]
temp = a[k];
a[k] = a[j];
a[j] = temp;
// Put tail end of permutation after jth position in increasing order
int r = a.length - 1;
int s = j + 1;
while (r > s) {
temp = a[s];
a[s] = a[r];
a[r] = temp;
r--;
s++;
}
numLeft = numLeft.subtract(BigInteger.ONE);
return a;
}
}
}
同时还有使用排列组合类的KPermutations类：
public class KPermutations<T> implements Iterable<List<T>> {
Combinations<T> combinations;
public KPermutations(List<T> list, int k) {
if (k<1){
throw new IllegalArgumentException("Subset length k must me at least 1");
}
combinations = new Combinations<T>(list, k);
}
public Iterator<List<T>> iterator() {
return new Iterator<List<T>>() {
Iterator<List<T>> it = combinations.iterator();
Permutations<T> permutations = new Permutations<T>(combinations.iterator().next());
// Has more combinations but no more permutation for current combination
public boolean hasNext() {
if (combinations.iterator().hasNext() && !permutations.iterator().hasNext()){
permutations = new Permutations<T>(combinations.iterator().next());
return true;
}
//Has more permutation for current combination
else if (permutations.iterator().hasNext()){
return true;
}
// No more combination and permutation
return false;
}
public List<T> next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return permutations.iterator().next();
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
}
- hrzafer
3
这里我有一个关于Scala的解决方案，它可以从Java中使用，但也可以通过更多的代码在Java中实现，允许使用迭代器来简化for循环：
for (List<Integer> list: permutations)
doSomething (list);
为了实现简化的for循环，我们需要实现Iterable接口，这意味着我们必须提供一个返回Iterator的方法，而Iterator又是另一个接口，这意味着我们必须实现3个方法：hasNext(); next(); 和remove();
import java.util.*;
class PermutationIterator <T> implements Iterator <List <T>> {
private int current = 0;
private final List <T> lilio;
public final long last;
public PermutationIterator (final List <T> llo) {
lilio = llo;
long product = 1;
for (long p = 1; p <= llo.size (); ++p)
product *= p;
last = product;
}
public boolean hasNext () {
return current != last;
}
public List <T> next () {
++current;
return get (current - 1, lilio);
}
public void remove () {
++current;
}
private long fac (long l)
{
for (long i = l - 1L; i > 1L; --i)
l *= i;
return l;
}
/**
new version, which produces permutations in increasing order:
*/
private List <T> get (final long code, final List <T> list) {
if (list.isEmpty ())
return list;
else
{
int len = list.size (); // len = 4
long max = fac (len); // max = 24
long divisor = max / len; // divisor = 6
int i = (int) (code / divisor); // i = 2
List <T> second = new ArrayList <T> (list.size ());
second.addAll (list);
T el = second.remove (i);
List <T> tt = new ArrayList <T> ();
tt.add (el);
tt.addAll (get (code - divisor * i, second));
return tt;
}
}
public List <T> get (final int code)
{
return get (code, lilio);
}
}
class PermutationIterable <T> implements Iterable <List <T>> {
private List <T> lilio;
public PermutationIterable (List <T> llo) {
lilio = llo;
}
public Iterator <List <T>> iterator () {
return new PermutationIterator <T> (lilio);
}
private long invers (final List <T> pattern, final List <T> matcher)
{
if (pattern.isEmpty ())
return 0L;
T first = pattern.get (0);
int idx = matcher.indexOf (first);
long l = (pattern.size () - 1L) * idx;
pattern.remove (0);
matcher.remove (idx);
return l + invers (pattern, matcher);
}
/**
make a deep copy, since the called method will destroy the parameters
*/
public long invers (final List <T> lt)
{
List <T> copy = new ArrayList <T> (lilio.size ());
copy.addAll (lilio);
return invers (lt, copy);
}
}
class PermutationIteratorTest {
public static List <Integer> genList (int... a) {
List <Integer> li = new ArrayList <Integer> ();
for (int i: a)
li.add (i);
return li;
}
public static void main (String[] args) {
List <Integer> il = new ArrayList <Integer> ();
// autoboxing, add '0' to 'z' as Character:
for (int c = 0; c < 3; ++c)
{
il.add (c);
}
PermutationIterable <Integer> pi = new PermutationIterable <Integer> (il);
for (List<Integer> li: pi)
show (li);
System.out.println ("-again-");
// do it a second time:
for (List <Integer> li: pi)
show (li);
// test the inverse:
System.out.println ("for (2,1,0) expecting 5 ?= " + pi.invers (genList (2, 1, 0)));
System.out.println ("for (2,0,1) expecting 4 ?= " + pi.invers (genList (2, 0, 1)));
System.out.println ("for (1,0,2) expecting 3 ?= " + pi.invers (genList (1, 2, 0)));
System.out.println ("for (1,2,0) expecting 2 ?= " + pi.invers (genList (1, 0, 2)));
System.out.println ("for (0,2,1) expecting 1 ?= " + pi.invers (genList (0, 2, 1)));
System.out.println ("for (0,1,2) expecting 0 ?= " + pi.invers (genList (0, 1, 2)));
Random r = new Random ();
PermutationIterator <Integer> pitor = (PermutationIterator <Integer>) pi.iterator ();
for (int i = 0; i < 10; ++i)
{
int rnd = r.nextInt ((int) pitor.last);
List <Integer> rli = pitor.get (rnd);
show (rli);
}
}
public static void show (List <?> lo) {
System.out.print ("(");
for (Object o: lo)
System.out.print (o);
System.out.println (")");
}
}
PermutationIterator包含一个额外的公共方法
public List <T> get (final int code)，如果你想通过索引挑选某个排列，比如随机挑选，这将非常方便。你知道大小（最后），因此可以通过索引来取有效范围内的排列。PermutationIterable包含一个方法'invers'，它将生成相反的内容：某个排列的索引。
在内部，invers和get是递归工作的，但并不是所有排列都是递归产生的，因此即使对于大排列，这也不应该是一个问题。请注意，对于21个元素，你会超过longs的大小，但20步递归完全不是问题。
- user unknown
3
你可以使用 Factoradics（你可以在这里看到实现）或生成所有排列的Knuth的L算法。以下是后者的实现：
public class Perm {
public static void main(String... args) {
final int N = 5;
int[] sequence = new int[N];
for (int i = 0; i < N; i++) {
sequence[i] = i + 1;
}
printSequence(sequence);
permutations(sequence);
}
private static int factorial(int n) {
int fact = 1;
for (int i = 1; i <= n; i++) {
fact *= i;
}
return fact;
}
private static void swap(int[] elements, int i, int j) {
int temp = elements[i];
elements[i] = elements[j];
elements[j] = temp;
}
/**
* Reverses the elements of an array (in place) from the start index to the end index
*/
private static void reverse(int[] array, int startIndex, int endIndex) {
int size = endIndex + 1 - startIndex;
int limit = startIndex + size / 2;
for (int i = startIndex; i < limit; i++) {
// swap(array, i, startIndex + (size - 1 - (i - startIndex)));
swap(array, i, 2 * startIndex + size - 1 - i);
}
}
private static void printSequence(int[] sequence) {
for (int i = 0; i < sequence.length; i++) {
System.out.printf("%d, ", sequence[i]);
}
System.out.println();
}
/**
* Implements the Knuth's L-Algorithm permutation algorithm
* modifying the collection in place
*/
private static void permutations(int[] sequence) {
final int N = sequence.length;
// There are n! permutations, but the first permutation is the array without
// modifications, so the number of permutations is n! - 1
int numPermutations = factorial(N) - 1;
// For every possible permutation
for (int n = 0; n < numPermutations; n++) {
// Iterate the array from right to left in search
// of the first couple of elements that are in ascending order
for (int i = N - 1; i >= 1; i--) {
// If the elements i and i - 1 are in ascending order
if (sequence[i - 1] < sequence[i]) {
// Then the index "i - 1" becomes our pivot index
int pivotIndex = i - 1;
// Scan the elements at the right of the pivot (again, from right to left)
// in search of the first element that is bigger
// than the pivot and, if found, swap it
for (int j = N - 1; j > pivotIndex; j--) {
if (sequence[j] > sequence[pivotIndex]) {
swap(sequence, j, pivotIndex);
break;
}
}
// Now reverse the elements from the right of the pivot index
// (this nice touch to the algorithm avoids the recursion)
reverse(sequence, pivotIndex + 1, N - 1);
break;
}
}
printSequence(sequence);
}
}
}
- higuaro
1
IEnumerable<IEnumerable<int>> generatePermutations(int length)
{
if (length <= 0) throw new ArgumentException();
var resultCollection = new List<IEnumerable<int>> { new [] { 0 } };
for (var index = 1; index < length; index++)
{
var newResultCollection = new List<IEnumerable<int>>();
foreach (var result in resultCollection)
{
for (var insertIndex = index; insertIndex >= 0; insertIndex--)
{
var list = new List<int>(result);
list.Insert(insertIndex, index);
newResultCollection.Add(list);
}
}
resultCollection = newResultCollection;
}
return resultCollection;
}
- Vladimir
1
当然，这已经做过了，其中一种解决方案是 Bells Permutation Algorithm。您可以在此处找到一个递归的Prolog解决方案和非递归的Pascal Bell排列算法。
将它们转换为Java留给读者作为练习。
将它们转换为Java留给读者作为练习。
- Anders
2
2虽然这个链接可能回答了问题，但最好在此处包含答案的基本部分并提供参考链接。如果链接页面更改，仅有链接的答案可能会失效。 - Achrome
是的，我知道。但重要的信息是算法的名称，而不是代码。但我理解这个问题。 - Anders
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接