没有递归的置换算法?爪哇 [英] 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.

有人可以帮我做吗?

推荐答案

你应该使用这样一个事实:当你想要 N 个数字的所有排列时，有 N 个！可能性.因此每个数字 x 来自 1..N！编码这样的排列.这是一个迭代打印出所有排列的示例.

You should use the fact that when you want all permutations of N numbers there are N! possibilities. Therefore each number x from 1..N! encodes such a permutation. Here is a sample that iteratively prints out all permutations of a sting.

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);
        }
    }

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