标签: permutation

我知道itertools,但它似乎只能生成排列而不重复.

例如,我想为2个骰子生成所有可能的骰子.所以我需要[1,2,3,4,5,6]的大小为2的所有排列,包括重复:(1,1),(1,2),(2,1)......等等

如果可能的话,我不想从头开始实现这一点

itertools.permutations根据其位置而不是其值来生成其元素被视为唯一的位置.所以基本上我想避免重复这样的:

>>> list(itertools.permutations([1, 1, 1]))
[(1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1), (1, 1, 1)]

之后进行过滤是不可能的,因为在我的情况下排列量太大了.

有人知道合适的算法吗？

非常感谢你!

编辑:

我基本上想要的是以下内容:

x = itertools.product((0, 1, 'x'), repeat=X)
x = sorted(x, key=functools.partial(count_elements, elem='x'))

这是不可能的,因为sorted创建一个列表并且itertools.product的输出太大.

对不起,我应该已经描述了实际问题.

numpy.random.shuffle(x)和之间有什么区别numpy.random.permutation(x)？

我已经阅读了doc页面,但是当我想随机改组数组元素时,我无法理解两者之间是否存在任何差异.

更确切地说,假设我有一个数组x=[1,4,2,8].

如果我想生成x的随机排列,那么shuffle(x)和之间的区别是permutation(x)什么？

我想生成一个集合(集合)的所有排列,如下所示:

Collection: 1, 2, 3
Permutations: {1, 2, 3}
              {1, 3, 2}
              {2, 1, 3}
              {2, 3, 1}
              {3, 1, 2}
              {3, 2, 1}

一般而言,这不是"如何"的问题,而是关于如何最有效的问题.此外,我不想生成所有排列并返回它们,但一次只生成一个排列,并且只在必要时继续(很像迭代器 - 我也尝试过,但结果却少了有效).

我已经测试了很多算法和方法,并提出了这个代码,这是我尝试过的最有效的代码:

public static bool NextPermutation<T>(T[] elements) where T : IComparable<T>
{
    // More efficient to have a variable instead of accessing a property
    var count = elements.Length;

    // Indicates whether this is the last lexicographic permutation
    var done = true;

    // Go through the array from last to first
    for (var i = …

查找包含k位的所有长度为n的二进制字符串的最佳算法是什么？例如,如果n = 4且k = 3,则有......

0111
1011
1101
1110

我需要一个很好的方法来生成这些给定任何n和任何k所以我更喜欢用字符串来完成它.

我正在尝试创建列表的排列列表,例如perms(list("a", "b", "c"))返回

list(list("a", "b", "c"), list("a", "c", "b"), list("b", "a", "c"),
     list("b", "c", "a"), list("c", "a", "b"), list("c", "b", "a"))

我不知道如何继续,任何帮助将不胜感激.

void permute(string elems, int mid, int end)
{
    static int count;
    if (mid == end) {
        cout << ++count << " : " << elems << endl;
        return ;
    }
    else {
    for (int i = mid; i <= end; i++) {
            swap(elems, mid, i);
            permute(elems, mid + 1, end);
            swap(elems, mid, i);
        }
    }
}

上面的函数显示了str(str[0..mid-1]作为一个稳定的前缀和str[mid..end]一个可置换的后缀)的排列.所以我们可以permute(str, 0, str.size() - 1)用来显示一个字符串的所有排列.

但该函数使用递归算法; 也许它的表现可以改善？

是否有更好的方法来置换字符串？

普遍认为n个不同符号的列表有n!排列.然而,当符号不明显时,在数学和其他地方最常见的惯例似乎只计算不同的排列.因此,列表的排列[1, 1, 2]通常被认为是
[1, 1, 2], [1, 2, 1], [2, 1, 1].实际上,以下C++代码正好打印出这三个:

int a[] = {1, 1, 2};
do {
    cout<<a[0]<<" "<<a[1]<<" "<<a[2]<<endl;
} while(next_permutation(a,a+3));

另一方面,Python itertools.permutations似乎打印其他东西:

import itertools
for a in itertools.permutations([1, 1, 2]):
    print a

这打印

(1, 1, 2)
(1, 2, 1)
(1, 1, 2)
(1, 2, 1)
(2, 1, 1)
(2, 1, 1)

正如用户Artsiom Rudzenka在一个答案中指出的那样,Python文档说:

元素根据其位置而不是其价值被视为唯一元素.

我的问题:为什么做出这个设计决定？

似乎遵循通常的惯例会给出更有用的结果(事实上它通常正是我想要的)......或者是否存在一些我缺少的Python行为应用？

[或者是一些实施问题？这里的算法next_permutation- 例如在StackOverflow上解释(由我)并在这里显示为O(1)摊销 - 在Python中似乎是高效和可实现的,但是Python做了更有效的事情,因为它不保证基于词典顺序价值？如果是这样,效率的提高是否值得呢？]

在Python中,我有一个n列表的列表,每个列表都有可变数量的元素.如何创建包含所有可能排列的单个列表:

例如

[ [ a, b, c], [d], [e, f] ]

我想要

[ [a, d, e] , [a, d, f], [b, d, e], [b, d, f], [c, d, e], [c, d, f] ]

注意我事先不知道n.我认为itertools.product是正确的方法,但它要求我提前知道参数的数量

我在编写代码时难以在JavaScript中生成包含m个元素的n个数组的组合.我已经在其他语言中看到了类似的问题,但答案包含语法或库魔法,我不确定如何翻译.

考虑这些数据:

[[0,1], [0,1,2,3], [0,1,2]]

3个数组,其中包含不同数量的元素.我想要做的是通过组合每个数组中的项来获得所有组合.

例如:

0,0,0 // item 0 from array 0, item 0 from array 1, item 0 from array 2
0,0,1
0,0,2
0,1,0
0,1,1
0,1,2
0,2,0
0,2,1
0,2,2

等等.

如果数组的数量是固定的,那么很容易进行硬编码实现.但阵列的数量可能会有所不同:

[[0,1], [0,1]]
[[0,1,3,4], [0,1], [0], [0,1]]

任何帮助将非常感激.