标签: permutation

如何在Python中生成列表的所有排列,与该列表中的元素类型无关？

例如:

permutations([])
[]

permutations([1])
[1]

permutations([1, 2])
[1, 2]
[2, 1]

permutations([1, 2, 3])
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

我有以下DataFrame:

    Col1  Col2  Col3  Type
0      1     2     3     1
1      4     5     6     1
...
20     7     8     9     2
21    10    11    12     2
...
45    13    14    15     3
46    16    17    18     3
...

从csv文件中读取DataFrame.所有具有Type1的行都在顶部,其次是具有Type2 的行,然后是具有Type3 的行等.

我想改组DataFrame的行,以便所有的行Type都是混合的.可能的结果可能是:

    Col1  Col2  Col3  Type
0      7     8     9     2
1     13    14    15     3
...
20     1     2     3     1
21    10    11    12     2
...
45     4     5     6 …

我一直Random (java.util.Random)用来洗牌一副52张牌.有52个!(8.0658175e + 67)可能性.然而,我发现种子java.util.Random是a long,它在2 ^ 64(1.8446744e + 19)处小得多.

从这里开始,我怀疑是否java.util.Random 真的那么随意 ; 它实际上能够生成所有52!可能性？

如果没有,我怎样才能可靠地生成一个更好的随机序列,可以产生所有52个!可能性？

编程访谈中的一个常见任务(不是根据我的访谈经验)是采用字符串或整数并列出每个可能的排列.

有没有这样做的例子和解决这个问题背后的逻辑？

我已经看过一些代码片段,但它们没有得到很好的评论/解释,因此难以理解.

我正在尝试编写一个执行以下操作的函数:

• 将整数数组作为参数(例如[1,2,3,4])
• 创建一个包含[1,2,3,4]所有可能排列的数组,每个排列的长度为4

下面的函数(我在网上找到)通过将一个字符串作为参数,然后返回该字符串的所有排列来完成此操作

我无法弄清楚如何修改它以使其与整数数组一起使用(我认为这与某些方法在字符串上的工作方式不同于它们在整数上的工作方式有关,但我不确定. ..)

var permArr = [], usedChars = [];
function permute(input) {
  var i, ch, chars = input.split("");
  for (i = 0; i < chars.length; i++) {
    ch = chars.splice(i, 1);
    usedChars.push(ch);
    if (chars.length == 0)
      permArr[permArr.length] = usedChars.join("");
    permute(chars.join(""));
    chars.splice(i, 0, ch);
    usedChars.pop();
  }
  return permArr
};

注意:我希望使函数返回整数数组,而不是字符串数组.

我真的需要使用JavaScript的解决方案.我已经在python中找到了如何做到这一点

说我有一个n个元素的列表,我知道有n个!订购这些元素的可能方式.生成此列表的所有可能排序的算法是什么？例如,我有列表[a,b,c].该算法将返回[[a,b,c],[a,c,b,],[b,a,c],[b,c,a],[c,a,b],[c,b , 一个]].

我在这里阅读 http://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations

但维基百科从未擅长解释.我不太了解它.

我有n个元素.为了举个例子,让我们说,7个元素,1234567.我知道有7个!=这些7个元素可能有5040个排列.

我想要一个包含两个函数的快速算法:

f(number)将0到5039之间的数字映射到唯一的排列,并且

f'(置换)将置换映射回其生成的数字.

我不关心数字和排列之间的对应关系,只要每个排列都有自己唯一的数字.

所以,举个例子,我可能会在哪里有功能

f(0) = '1234567'
f'('1234567') = 0

想到的最快的算法是枚举所有排列并在两个方向上创建查找表,这样,一旦创建表,f(0)将是O(1)并且f('1234567')将是查找字符串.然而,这是内存饥饿,特别是当n变大时.

任何人都可以提出另一种算法,它可以快速工作,没有内存缺点吗？

我很好奇如何std:next_permutation实现,所以我提取了gnu libstdc++ 4.7版本并清理了标识符和格式以生成以下演示...

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

template<typename It>
bool next_permutation(It begin, It end)
{
        if (begin == end)
                return false;

        It i = begin;
        ++i;
        if (i == end)
                return false;

        i = end;
        --i;

        while (true)
        {
                It j = i;
                --i;

                if (*i < *j)
                {
                        It k = end;

                        while (!(*i < *--k))
                                /* pass */;

                        iter_swap(i, k);
                        reverse(j, end);
                        return true;
                }

                if (i == begin) …

我有这样的数据帧(df1).

     f1   f2   f3   f4   f5
d1   1    0    1    1    1  
d2   1    0    0    1    0
d3   0    0    0    1    1
d4   0    1    0    0    1

d1 ... d4列是rowname,f1 ... f5行是列名.

为了做样本(df1),我得到一个与df1相同的新数据帧.因此,对于整个数据帧,计数1是保留的,但对于每行或每列都不是.

是否可以逐行或逐列进行随机化？

我想为每列随机化df1列,即每列中1的数量保持不变.每列需要更改至少一次.例如,我可能有一个像这样的随机df2 :(注意每列中的1的计数保持不变,但每行中的1的计数是不同的.

     f1   f2   f3   f4   f5
d1   1    0    0    0    1  
d2   0    1    0    1    1
d3   1    0    0    1    1
d4   0    0    1    1    0

同样,我也想为每一行逐行随机化df1,即no.每行中1的值保持不变,并且每行都需要更改(但更改的条目的数量可能不同).例如,随机化的df3可能是这样的:

     f1   f2   f3   f4   f5
d1   0    1    1    1    1 …

我有一个字符串.我想通过改变字符串中的字符顺序从该字符串生成所有排列.例如,说:

x='stack'

我想要的是这样的列表,

l=['stack','satck','sackt'.......]

目前我正在迭代字符串的列表转换,随机挑选2个字母并转置它们以形成一个新字符串,并将其添加到l的设置转换.根据字符串的长度,我计算可能的排列数,并继续迭代,直到设置大小达到限制.必须有更好的方法来做到这一点.