3

例如，假设我想生成两个值的所有排列，每个可能是 0 或 1，我会得到：

[11,10,01,00]

注意这里第一个变量变化最慢，所以它保持固定而其余变量变化。

在三个变量的情况下，我会得到

[111,110,101,100,011,010,001,000]

我看到它应该有一个递归定义，但在我的脑海中还不够清楚，所以我可以表达它。

4

5 回答 5

24

这不是关于排列，而是关于组合，您可以在 Haskell 中轻松生成它们：

replicateM 3 "01"
= ["000","001","010","011","100","101","110","111"]

如果您需要实际的整数：

replicateM 3 [0, 1]
= [[0,0,0],[0,0,1],[0,1,0],[0,1,1],
   [1,0,0],[1,0,1],[1,1,0],[1,1,1]]

最后，如果各个位置的值不同：

sequence [".x", ".X", "-+"]
= ["..-","..+",".X-",".X+","x.-","x.+","xX-","xX+"]

当然，这也适用于整数：

sequence [[0,1], [0,2], [0,4]]
= [[0,0,0],[0,0,4],[0,2,0],[0,2,4],
   [1,0,0],[1,0,4],[1,2,0],[1,2,4]]
于 2013-03-17T03:36:31.070 回答
2

如果您想要排列，例如在列表列表中，这是使用列表单子的解决方案。

\n -> mapM (const [0, 1]) [1..n]
于 2013-03-17T03:02:32.137 回答
1 
ghci> :m +Data.List
ghci> permutations [0,1]
[[0,1],[1,0]]
于 2013-03-17T06:49:18.700 回答
1

(Edited based on feedback)

The smallest n-digit binary integer is 000..0 (n times), which is 0.

The largest n-digit binary integer is 111...1 (n times), which is 2^n - 1.

Generate the integers from 0 to 1<<n - 1 and print out the values you have.

Haskell's Int should be safe for <= 28 binary variables.

Hope that helps.

于 2013-03-17T03:01:35.800 回答
-3

我不知道haskel，但这里有一段关于我如何进行排列的伪代码。

var positions = [0,0,0];
var max = 1;

done:
while(true){
    positions[0]++; //Increment by one
    for (var i = 0; i < positions.length; i++) {
        if(positions[i] > max){ //If the current position is at max carry over
            positions[i] = 0;
            if(i+1 >= positions.length){ //no more positions left
                break done; 
            }
            positions[i+1]++;
        }
    }
}
于 2013-03-17T03:14:58.597 回答