编写一个方法，每次调用时输出一个数字的不同唯一排列

Question

我拿到了这个面试题，但我仍然很困惑。问题如题，我来解释一下。

你有一个随机创建函数可以使用。

函数输入为整数n。假设我用 3.

来称呼它

它应该给我 1 - 3 的数字排列。例如，它会给我 2、3、1。

在我再次调用该函数后，它不会给我相同的排列，现在它会给我 1、2、3 例如。

现在如果我用 n = 4 调用它。我可能会得到 1,4,3,2。

再次用 3 调用它不会像之前那样输出 2,3,1 或 1,2,3，它会给我一个不同的 3 排列！可能的排列。

我当时对这个问题很困惑，现在还是。在正常运行时间内这怎么可能？正如我所见，必须有一些静态变量来记住函数完成执行之前或之后调用的内容。所以我的想法是创建一个静态哈希表（键，值），它将输入作为键，值是 n! 长度的数组。然后我们使用随机方法从这些中输出一个随机实例并将这个实例移到后面，所以它不会被再次调用，从而保持输出的唯一性。

space 时间复杂度对我来说似乎很大。我在这个问题中遗漏了什么吗？

Answer 1

您可以将静态变量存储为下一个排列的种子

在这种情况下，我们可以使用 int 更改每个数字将放入哪个插槽（例如，这被硬编码为 4 个数字的集合）

private static int seed = 0;

public static int[] generate()
{
    //s is a copy of seed, and increment seed for the next generation
    int s = seed++ & 0x7FFFFFFF; //ensure s is positive
    int[] out = new int[4];

    //place 4-2
    for(int i = out.length; i > 1; i--)
    {
        int pos = s % i;
        s /= i;
        for(int j = 0; j < out.length; j++)
            if(out[j] == 0)
                if(pos-- == 0)
                {
                    out[j] = i;
                    break;
                }
    }

    //place 1 in the last spot open
    for(int i = 0; i < out.length; i++)
        if(out[i] == 0)
        {
            out[i] = 1;
            break;
        }

    return out;
}

这是一个将大小作为输入，并使用 HashMap 存储种子的版本

private static Map<Integer, Integer> seeds = new HashMap<Integer, Integer>();

public static int[] generate(int size)
{
    //s is a copy of seed, and increment seed for the next generation
    int s = seeds.containsKey(size) ? seeds.get(size) : 0; //can replace 0 with a Math.random() call to seed randomly
    seeds.put(size, s + 1);
    s &= 0x7FFFFFFF; //ensure s is positive
    int[] out = new int[size];

    //place numbers 2+
    for(int i = out.length; i > 1; i--)
    {
        int pos = s % i;
        s /= i;
        for(int j = 0; j < out.length; j++)
            if(out[j] == 0)
                if(pos-- == 0)
                {
                    out[j] = i;
                    break;
                }
    }

    //place 1 in the last spot open
    for(int i = 0; i < out.length; i++)
        if(out[i] == 0)
        {
            out[i] = 1;
            break;
        }

    return out;
}

此方法有效，因为种子存储了要放置的每个元素的位置

尺码 4：

获取以 4 为基数的最低位，因为还有 4 个空位
在该位置放置一个 4
移动数字以删除使用的数据（除以 4）
获取基数 3 中的最低位，因为还有 3 个空位
在该位置放置一个 3
移动数字以删除使用的数据（除以 3）
获取基数 2 中的最低位，因为还有 2 个空位
在该位置放置一个 2
移动数字以删除使用的数据（除以 2）
仅剩1个名额
在该位置放置一个 1

此方法最多可扩展到12个！对于整数，13！溢出，还是20！对于多头（21！溢出）

如果您需要使用更大的数字，您可以将种子替换为 BigIntegers

Answer 2

Jonathan Rosene 的回答被否决了，因为它是 link-only，但在我看来它仍然是正确的答案，因为这是一个众所周知的问题。您还可以在维基百科中看到最简单的解释：https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order.

为了解决您的 space-复杂性问题，按字典顺序生成排列具有 O(1) space 复杂性，除了当前排列之外，您不需要存储任何内容。该算法非常简单，但最重要的是，它的正确性非常直观。想象一下，您拥有所有排列的集合，并按字典顺序对它们进行排序。按顺序前进到下一个然后循环返回将为您提供最大循环而不会重复。问题又是 space-复杂性，因为您需要存储所有可能的排列；该算法为您提供了一种无需存储任何内容即可获得下一个排列的方法。可能需要一段时间才能理解，但是一旦我明白了，它很有启发性。

编写一个方法，每次调用时输出一个数字的不同唯一排列

Writing a method that outputs a different uniqe permutation of a number every time it's called

java

random

algorithm

hashtable

permutation