3

如何从 中一一（不重复）随机选择所有结果itertools.permutations(k)？或者这个：如何构建随机排列的生成器？类似的东西shuffle(permutations(k))。我正在使用 Python 2.6。

是的，shuffle(r)可以使用 if ，但是当提升到 10 以上r = list(permutations(k))时，这样的列表会占用太多的时间和内存。len(k)

谢谢。

4

6 回答 6

4

这给出了列表的第 n 个排列

def perm_given_index(alist, apermindex):
    alist = alist[:]
    for i in range(len(alist)-1):
        apermindex, j = divmod(apermindex, len(alist)-i)
        alist[i], alist[i+j] = alist[i+j], alist[i]
    return alist

和apermindex之间在哪里0factorial(len(alist))

于 2011-04-09T02:58:30.300 回答
2

我不知道python是如何实现它的shuffle算法的，但是以下是线性时间的，所以我不明白为什么10的长度这么重要（除非我误解了你的问题？）：

  • 从项目列表开始；
  • 依次遍历列表中的每个索引，将该索引处的项目交换为列表其余部分中随机索引处的项目（包括项目本身）。

对于不同的排列，只需再次运行相同的算法。

于 2011-04-09T02:31:32.343 回答
2

如果不编写自己的permutations.

考虑一下：

  • 我们有一个包含结果的生成器对象permutations。
  • 我们编写了自己的函数来告诉我们生成器的长度。
  • 然后我们在列表的开头和结尾之间随机选择一个条目。

由于我有一个生成器，如果随机函数在列表末尾附近选择一个条目，那么获得它的唯一方法是遍历所有先前的条目并将它们扔掉，这很糟糕，或者将它们存储在一个列表中，当您有很多选择时，您已经指出这是有问题的。

你是要遍历每一个排列还是只使用几个？如果是后者，那么随机生成每个新排列并将然后存储在set. 如果您不使用那么多，那么每次发生碰撞时都必须创建新排列的开销将非常低。

于 2011-04-09T06:04:24.220 回答
1

有一些算法可以给你排列。您可以在这篇wikipedia article中找到一个在线性时间内工作的。

在 python 中实现它以yield实现高效的顺序生成。但是，如果您想要不重复的随机选择，您必须生成列表，或者使用Dan发布的算法并记住您已经选择的数字。

于 2011-04-09T03:09:06.657 回答
1

您正在寻找的是 Lehmer 指数。Lehmer 索引可以从一个随机整数生成，然后可以转换为一个特定的排列，所有这些都不需要生成一组排列，只有您实际使用的一个排列。

知道你想要 n 个对象的 n 个排列之一，你就知道有 n! 其中。您需要做的就是选择一个介于 0 和 n!-1 之间的数字，然后使用 Lehmer 代码将您的 base-10 索引转换为 Lehmer 代码，然后它将成为一个阶乘基数。这些数字也称为factoradics。

例如，假设您要选择索引为 0、1 和 2 的 3 个对象的特定随机排列。 (0, 1, 2)（全部按顺序）的 Lehmer 代码将是 (0, 0, 0)，其中前两个零很重要，因为最后一个零是 0！永远为零的地方。所以只考虑前两个。那么置换 (0, 1, 2) 的 Lehmer 码将是 (0, 0)，因为每个数字子集中的反转数是 0，即 (0, 1, 2) 没有反转（因为 0 < 1 < 2) 和 (1, 2) 没有反转（因为 1 < 2）。

另一个例子是 (2, 1, 0)。要获得此代码的 Lehmer 代码，您将以相同的方式计算反转。(2, 1, 0) 整体有 2 个反转（因为 2 > 1 和 1 > 0），子排列 (1, 0) 有 1 个版本（因为 1 > 0）。所以这将给出 (2, 1) 作为 Lehmer 代码。如果我们添加始终存在的零，那么这将产生 Lehmer 码 (2, 1, 0)。

那么你将如何使用它呢？每个 Lehmer 代码都有一个对应的以 10 为底的数字，因为每个数字位置都有一个位值。在上面的 (2, 1, 0) 的情况下，我们有 2 * 2！+ 1 * 1！+ 0 * 0！= 4 + 1 + 0 = 5。现在您可以选择一个随机数，例如 5，然后生成 Lehmer 码，然后生成特定的排列，而无需全部生成。

这是我不久前写的一些代码来做到这一点。它将 Lehmer 代码称为radix，以免混淆。这是来自我在 GitHub 上的 util 存储库。

/**
 * Given a factoradic index, this function computes the radix form of the
 * index. That is, it converts the base 10 input index into a non-constant
 * factorial base number.
 */
long int factoradic_radix_index_long( long int dim_in, long int idx_in, long int *rad_out )
{
    long int i,fct,div,rem;

    rem = idx_in;
    for(i=dim_in-1;i>=0;i--)
    {
        fct = factorial( i );
        div = rem / fct;
        rem = rem % fct;
        rad_out[dim_in-1-i] = div;
    }
}

要了解如何从基数向量（Lehmer 代码）中获得实际排列，这里有一个示例，它完成了从以 10 为底的排列索引到排列的整个转换。

long int factoradic_vector_long( long int idx_in, long int dim_in, long int *vec_out )
{
    long int i,j,k,rad[dim_in];
    int fnd[dim_in];

    for(i=0;i<dim_in;i++)
        fnd[i] = 0;

    factoradic_radix_index_long( dim_in, idx_in, rad );

    for(i=0;i<dim_in;i++)
    {
        for(j=0,k=0;j<dim_in;j++)
        {
            if( fnd[j] == 0 )
                ++k;
            if( k - 1 >= rad[i] )
                break;
        }
        fnd[j] = 1;
        vec_out[i] = j;
    }
    return 0;
}
于 2020-08-03T16:25:06.893 回答
0

也许这不是那么有效，但它允许处理给定列表的任意数量的随机排列。 

import numpy as np
from math import factorial

for i in range(factorial(len(biglist))):
    permut = np.random.permutation(biglist).tolist()
    ...
于 2014-02-20T18:50:42.267 回答