问题标签 [permutation]

我需要迭代地计算排列。方法签名如下所示：

int[][] permute(int n)

例如n = 3，返回值将是：

您将如何以最有效的方式迭代地执行此操作？我可以递归地执行此操作，但我有兴趣看到许多替代方法来迭代地执行此操作。

我正在寻找并从中map<char, vector<char> >生成每一个可能map<char, char>的结果。

我知道这可能会使用大量内存并需要一些时间。

每个都map<char, char>需要包含每个字母 az，并映射到唯一的 az 字符。IE。ak bj cp dy ev fh ga hb ir jq kn li mx nc oo pz qs rl sd te uw vf wg xm yu zt

到目前为止，这是我为自己得出的结论：

为了将可能组合的荒谬数量减少到较低的数量，如果 avector<char>包含超过 5 个元素，我将简单地将其替换为vector<char>包含来自我的 'master'/'original' 的单个字符的 a map<char, char>。

并非所有字符都会出现vector<char>s在地图的所有区域中。需要找到这些字符并将其放入一些“其他”向量中。

这还应该包含一个字符是多个字符键的唯一可能字符的字符（即我正在使用的示例中的 mw - 我不确定如何处理）。

此“其他”向量应用于不可能具有唯一 az 字符或多个字符具有相同的单个可能字符的情况。

这是我到目前为止的一个例子。

我将采取map<char, vector<char> >，例如：

a: gjkpqvxz
b: gjkpqvxz
c: gjkpqvxyz
d: mw
e: gjkpqvxz
f: nr
g: at
h: cf
i: his
j: gjkpqvxz
k: r
l: h
m: gjkpqvxz
n: gjkpquvxyz
o: is
p: gjkpqvxz
q:是
r: dl
s: l
t: e
u: dgkpuvy
v: cf
w:
bcf x: dguy
y: f
z: at

这是我的起始地图。在切出超过 5 个的大字符向量并用最佳猜测替换它们之后。如果 avector<char>的大小为 1，则该字符映射只有一个组合，并且该字符不能用于任何其他映射，因为它会使其不唯一。我已将其修剪为：

a: k
b: j
c: p
d: mw
e: v
f: n
g: at
h: c
i: is
j: q
k: r
l: h
m: x
n: guy
o: is
p: z
q:是
r: d
s: l
t: e
u: dguy
v: c
w: bc
x: dguy
y: f
z: at

'others' 向量包含 'o' （我认为重要的是要注意，我认为这应该包含上面示例中的 mw 等情况。因为 d 是唯一可以使用 mw 的地方，但显然需要每个字母只能使用一次，只能使用其中一个，而另一个则丢失在某个地方。我不知道如何编写一个一般案例来将这些添加到其他向量中。）

我正在寻找帮助和指示，以生成像这样和这种格式的所有可能map<char, char>。map<char, vector<char> >s它们将用作函数调用中的参数。我不确定从哪里开始写一些一般意义上的东西。我可能会用大量的 for 循环来处理它.

对不起，如果这太像文字墙，或者看起来过于具体或写得不好/问得不好。

我感谢任何和所有的帮助。

生成给定字符串的所有可能字母组合的算法，低至 2 个字母

尝试在 AS3 中创建一个 Anagram 求解器，例如在这里找到的这个：

http://homepage.ntlworld.com/adam.bozon/anagramsolver.htm

我在为各种长度的字符串生成所有可能的字母组合时遇到了问题。如果我只生成固定长度的排列，这对我来说不会是一个问题......但我希望减少字符串的长度并从原始字母集中获得所有可能的排列最大长度小于原始字符串的字符串。例如，假设我想要一个长度为 2 的字符串，但我有一个 3 字母的“abc”字符串，输出将是：ab ac ba bc ca cb。

理想情况下，该算法会生成一个完整的可能组合列表，从原始字符串长度开始，一直到最小的字符串长度 2。我觉得可能有一个小的递归算法可以做到这一点，但无法绕开我的大脑它。我在 AS3 工作。

谢谢！

Python 的itertools模块提供了很多关于使用生成器处理可迭代/迭代器的好东西。例如，

Ruby 中的等价物是什么？

等效，我的意思是快速和高效的内存（Python 的 itertools 模块是用 C 编写的）。

假设我们有一个像

我想以x某种惯用的方式计算元素之间的最大距离。迭代 ' 元素的所有可能组合很容易，x但我觉得可能有一种方法可以用 MATLAB 的内置函数以某种疯狂但惯用的方式来实现。

我正在寻找一种算法，它给定序列的两个排列（例如[2, 3, 1, 4]和[4, 1, 3, 2]）计算将第一个转换为第二个所需的周期[[0, 3], [1, 2]]（例如， ）。

来自 mathworld 的链接说 Mathematica 的 ToCycle 函数可以做到这一点，但遗憾的是我手头没有任何 Mathematica 许可证......我很乐意收到任何指向任何 FOSS 语言或数学包中算法实现的指针。

谢谢！

这更像是一个数学问题而不是编程，但我认为这里的很多人都非常擅长数学！:)

我的问题是：给定一个 9 x 9 网格（81 个单元格），每个网格必须包含数字 1 到 9 恰好 9 次，可以生成多少个不同的网格。数字的顺序无关紧要，例如第一行可能包含九个 1 等。这与数独有关，我们知道有效数独网格的数量是 6.67×10^21，所以因为我的问题不受限制就像数独一样，必须在每一行、每一列和每一框中都有 9 个数字，那么答案应该大于 6.67×10^21。

我的第一个想法是答案是 81！然而，进一步思考，这假设每个单元格可能的 81 个数字是不同的、不同的数字。它们不是，每个单元格有 81 个可能的数字，但只有 9 个可能的不同数字。

我的下一个想法是，第一行中的每个单元格都可以是 1 到 9 之间的任何数字。如果碰巧第一行恰好都是相同的数字，比如说全 1，那么第二行中的每个单元格只能有 8 种可能性，2-9。如果这一直持续到最后一行，则可以通过 9^2 * 8^2 * 7^2 ..... * 1^2 计算不同排列的数量。但是，如果每行不包含 9 个相同的数字，这将不起作用。

自从我研究这些东西以来已经有一段时间了，我想不出办法来解决它，我将不胜感激任何人可以提供的帮助。

考虑一个带有 n 个卷轴的典型老虎机（比如 reel1：a、b、c、d、w1、d、b、..etc）。
在游戏中，我们生成一个连接的 n 个对象字符串（如上面的字符） 我们有一个赔付表，其中列出了带有支付金额的获胜字符串。

问题是可以替换 {w1:a,b,c},{w2:a} ..etc 的通配符（通配符列表：w1,w2）。是否值得预先计算和使用所有可能的获胜字符串排列，或者只是在发生时，相应地生成所有具有手头模式的组合。

最初我并没有真正看到太大的不同，但现在如果我需要扩展机器以处理 11 个以上的卷轴，并且比以前更加集中，我需要找出这个特定位的确切方法。

任何想法都将不胜感激:)

有人可以解释itertools.permutationsPython 标准库 2.6 中的例程算法吗？我不明白为什么它有效。

代码是：

Possible Duplicate:
How do you efficiently generate a list of K non-repeating integers between 0 and an upper bound N

What are some alternative methods to generate 1000 distinct random integers in the range [0,8000] as opposed to the following:

1. naive method: generating a number and checking if it's already in the array. O(n^2)
2. linear shuffle: generate sequence 0 to 8000, shuffle, take the first 1000. O(n)