不使用递归的排列算法？Java

Question

不使用递归的排列算法？Java

43

我希望能够获取一个数字的所有组合，且没有重复。像0.1.2、0.2.1、1.2.0、1.0.2、2.0.1、2.1.0这样。我试图找到一个简单的方法，但是失败了。我画了一张图/树来解决它，这正呼唤着使用递归。但如果可能的话，我想不用递归来做这个。

请问有人可以帮我吗？

- Andreas Hornig

5

递归是解决这个问题的自然方法。为什么你想在不适用递归的情况下解决它呢？任何明智的“非递归”解决方案最终都会使用单独的堆栈来模拟递归。 - Greg Hewgill

3

@Greg 可读性呢？很多人发现递归难以理解 - 不使用递归也许会使意图更加明确？ - Robben_Ford_Fan_boy

4

需要支持这种说法，需要一个更易读的非递归解决方案的例子。 - Greg Hewgill

1

我怀疑可以找到一些公式，可以将排列元素的值作为计数的函数来给出。类似于f(seq,len,place)=(seq!place)%len..（当然不是这个，我还没有破解）。但我可以看出，能够以公式的形式表达唯一排列模式的细节可能非常有用。 - strainer

一个非递归的解决方案是贝尔置换算法，就像我在答案中描述的那样。 - Anders

显示剩余5条评论

13个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- PirateApp · Answer 1

@Filip Nyugen提供的解决方案是针对那些想要使用JS获得答案的人。

function printPermutationsIterative(string) {
    const factorials = [];
    factorials[0] = 1;
    for (let i = 1; i <= string.length; i++) {
        factorials[i] = factorials[i - 1] * i;
    }

    for (let i = 0; i < factorials[string.length]; i++) {
        let onePermutation = "";
        let temp = string;
        let positionCode = i;
        for (let position = string.length; position > 0; position--) {
            let selected = positionCode / factorials[position - 1];
            onePermutation += temp.charAt(selected);
            positionCode = positionCode % factorials[position - 1];
            temp = temp.substring(0, selected) + temp.substring(selected + 1);
        }
        console.log(onePermutation);
    }
}

- Sleem · Answer 2

这是一个简单的Java函数，用于打印所有可能的排列（包括较小的空字符串“”）。如果您只需要打印相同长度的排列，请在打印之前添加if语句。

这个想法与递归相同。但是，我们使用数据结构（在此示例中为列表）来堆叠排列，而不是堆叠方法调用。

import java.util.LinkedList;
import java.util.List;


    public class Permutations {

        public void perm(String input) {
            List<String[]> buffer = new LinkedList<>();
            buffer.add(new String[]{input, ""});
            while (!buffer.isEmpty()) {
                String[] perm = buffer.remove(0);
                System.out.println(perm[1]);
                for (int i = 0; i < perm[0].length(); i++) {
                    buffer.add(new String[]{perm[0].substring(0, i) + perm[0].substring(i + 1), perm[1] + perm[0].charAt(i)});
                }
            }
        }

    }

- ArK · Answer 3

import java.io.*;
class Permutation
{
String w;

public void accept() throws IOException 
{ BufferedReader ak=new BufferedReader(new InputStreamReader(System.in)); System.out.println("Enter a word"); w=ak.readLine(); }

public void permute()
{
int l,s,m,p,k,t,x,n,r;
s=m=0;p=t=k=1;
l=w.length();
for(x=1;x<=l;x++)
{
p*=x; s+=x; t*=10;
}
System.out.println("\n"+"The "+p+" possible permutations of the word are:"+"\n");
for(x=t/10;x

public boolean isUnique(int n) {
int a[]={0,0,0,0,0,0,0,0,0,0};
int r;
while(n!=0)
{
r=n%10;
if(a[r]!=0 || r==0)
return false;
else
a[r]++;
n/=10;
}
return true;
}
}