arrays - 给定数字中所有可能的数字排列

Question

用户应该输入他的号码有多少位，然后他应该输入他的号码。然后代码应该以所有可能的方式排列该数字，而不是递归。

例如，数字 123 可以按 6 种方式排列：

123 132 213 231 312 321

只是一个旁注，如果我问这个问题的方式有问题，或者如果需要更多信息，请告诉我。即使你不知道我的问题的答案。我真的需要回答这个问题，我想我开始为此发疯了。

Answer 1

This is equivalent to generating all permutations.

For generating the next permutation after the current one(the first one is 123):
  1. Find from right to left the first position pos where current[pos] < current[pos + 1]
  2. Increment current[pos] to the next possible number(some numbers are maybe already used)
  3. At the remaining positions(> pos) put the smallest possible numbers not used.
  4. Go to 1.

Here is a working code, printing all permutations:

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

    public static void main(String[] args) {
        final int n = 3;

        int[] current = new int[n];
        for (int i = 1; i <= n; i++) {
            current[i - 1] = i;
        }

        int total = 0;
        for (;;) {
            total++;

            boolean[] used = new boolean[n + 1];
            Arrays.fill(used, true);

            for (int i = 0; i < n; i++) {
                System.out.print(current[i] + " ");
            }

            System.out.println();

            used[current[n - 1]] = false;

            int pos = -1;
            for (int i = n - 2; i >= 0; i--) {              
                used[current[i]] = false;

                if (current[i] < current[i + 1]) {
                    pos = i;
                    break;
                }
            }

            if (pos == -1) {
                break;
            }               

            for (int i = current[pos] + 1; i <= n; i++) {
                if (!used[i]) {
                    current[pos] = i;
                    used[i] = true;
                    break;
                }
            }

            for (int i = 1; i <= n; i++) {
                if (!used[i]) {
                    current[++pos] = i;
                }
            }
        }

        System.out.println(total);
    }       
}

P.S. I wrote the code just now in a couple of minutes. I don't claim that the code is clean or the variables are named good.

Answer 2

稍微搜索一下，你会发现一些算法，例如Johnson-Trotter 算法，它可以用 5 行来描述：

用 <1 <2 ... <n 初始化第一个排列
虽然存在一个移动整数
  找到最大的移动整数 k
  交换 k 和它正在查看的相邻整数
  反转所有大于 k 的整数的方向