标签: permutation

我想有一个归纳类型来描述排列及其对某些容器的行为.很明显,根据这种类型的描述,算法的定义复杂度(就其长度而言)(计算组合或逆,分解成不相交的循环等)将会变化.

考虑Coq中的以下定义.我认为这是Lehmer代码的形式化:

Inductive Permutation : nat -> Set :=
| nil : Permutation 0
| cons : forall (n k : nat), Permutation (k + n) -> Permutation (k + S n).

很容易在大小为n的向量上定义它的动作,在其他容器上稍微硬一些,并且(至少对我而言)很难找到组合的形式化或逆向.

或者,我们可以将置换表示为具有属性的有限映射.可以容易地定义组合或逆,但是将其分解成不相交的循环是困难的.

所以我的问题是:是否有任何文件可以解决这个权衡问题？我设法找到的所有工作都处理了命令式设置中的计算复杂性,而我对"推理复杂性"和函数式编程感兴趣.

给定PHP字符串数组,例如:

['peter', 'paul', 'mary']

如何生成此数组元素的所有可能排列？即:

peter-paul-mary
peter-mary-paul
paul-peter-mary
paul-mary-peter
mary-peter-paul
mary-paul-peter

这是一段时间前谷歌采访中向我的朋友询问的问题.他无法提出解决方案,但无论如何最终还是把这份工作打包好了.这是问题所在

您已经获得300个数字,包括100个数字,100个二进制和100个三分数,现在提出了一个算法,将确定所有这些数字,这是一个完美的正方形

我尝试了一段时间,但我很难过.有关如何去做的任何想法？

给定一个字符串,我想生成所有可能的组合.换句话说,将逗号放在字符串中的所有可能方法.

例如:

input:  ["abcd"]
output: ["abcd"]
        ["abc","d"]
        ["ab","cd"]
        ["ab","c","d"]
        ["a","bc","d"]
        ["a","b","cd"]
        ["a","bcd"]
        ["a","b","c","d"]

我有点坚持如何生成所有可能的列表.组合将只给出包含字符串集子集长度的列表,排列将提供所有可能的订购方式.

由于遍历切片,我可以在列表中只使用一个逗号来创建所有情况,但是我不能用两个逗号来表示例如"ab","c","d"和"a","b" ,"光盘"

我的尝试w/slice:

test="abcd"

for x in range(len(test)):
     print test[:x],test[x:]

我想知道下面解释的任务是否在理论上是可行的,如果是这样,我怎么能做到.

给你一个N元素空间(即0和之间的所有数字N-1.)让我们看看那个空间上所有排列的空间,然后调用它S.可以标记的i第th个成员是带有词典编号的排列.SS[i]i

例如,如果N是3,那么S这个排列列表是:

S[0]: 0, 1, 2
S[1]: 0, 2, 1
S[2]: 1, 0, 2
S[3]: 1, 2, 0
S[4]: 2, 0, 1
S[5]: 2, 1, 0

(当然,当看到一个大的时候N,这个空间变得非常大,N!确切地说.)

现在,我已经知道如何通过其索引号来获得排列i,并且我已经知道如何反转(得到给定排列的词典编号.)但我想要更好的东西.

一些排列本身可能很大.例如,如果你正在看N=10^20.(的大小S将是(10^20)!我相信这是我在一个堆栈溢出问题提起过的最大号:)

如果你只是在那个空间上看一个随机的排列,那么你将无法将整个东西存储在你的硬盘上,更不用说通过词典编号来计算每个项目了.我想要的是能够对该排列进行项目访问,并获得每个项目的索引.也就是说,给定N和i指定一个排列,有一个函数接受一个索引号并找到该索引中的数字,另一个函数接受一个数字并找到它所在的索引.我想这样做O(1),所以我不需要在排列中存储或迭代每个成员.

你说疯了吗？不可能？那可能.但请考虑一下:像AES这样的分组密码本质上是一种排列,它几乎完成了我上面概述的任务.AES具有16个字节的块大小,这意味着N是256^16它是围绕10^38.(S重要的是,它的大小是一个惊人的(256^16)!,或者说是围绕着10^85070591730234615865843651857942052838 …

我正在阅读Accelerated C++.我不明白练习5-1:

设计并实现一个程序,从以下输入产生置换索引.置换索引是指每个短语由短语中的每个单词索引的索引.

     The quick      brown fox 
jumped over the     fence
The quick brown     fox 
                    jumped over the fence
         jumped     over the fence
            The     quick brown fox 
    jumped over     the fence
                    The quick brown fox

这个解释对我来说并不清楚.什么是置换索引？

在这个主题中,我试图在这里包括所有常见问题及其答案.我希望这对某人有用.

一般问题:如何r从n对象生成对象序列？

• 组合与排列.
• 有替换和没有替换.
• 不同的项目与非独特的项目(多重集合).

总共存在这类2^3=8问题.

[更新]

Josh O'Brien认为这8个问题与十二种方式有关.实际上,"不同"的问题以十二种方式包含在内,而"非独特"的问题则不包括在内.无论如何,将这里的8个问题与12倍的方式进行比较是很有趣的.请参阅注释以获取进一步的读数.

我在javascript中有一个n个不同元素的数组,我知道有n个!订购这些元素的可能方式.我想知道什么是最有效(最快)的算法来生成这个数组的所有可能的排序？

我有这个代码:

var swap = function(array, frstElm, scndElm) {

    var temp = array[frstElm];
    array[frstElm] = array[scndElm];
    array[scndElm] = temp;
}

var permutation = function(array, leftIndex, size) {

    var x;

    if(leftIndex === size) {

        temp = "";

        for (var i = 0; i < array.length; i++) {
            temp += array[i] + " ";
        }

        console.log("---------------> " + temp);

    } else {

        for(x = leftIndex; x < size; x++) {
            swap(array, leftIndex, x);
            permutation(array, leftIndex + 1, size);
            swap(array, leftIndex, x);
        } …

在Python中,使用itertools模块生成列表的所有排列非常简单.我有一种情况,我使用的列表只有两个字符(即'1122').我想生成所有独特的排列.

对于字符串'1122',有6个唯一的排列(1122,1212,1221等),但itertools.permutations将产生24个项目.仅记录唯一排列很简单,但是由于考虑了所有720个项目,因此收集它们所需的时间要长得多.

是否有一个函数或模块在生成排列时会考虑重复的元素,所以我不必自己编写？

我试图生成所有可能的方法来交错Python中的任意两个任意字符串.

例如:如果两个字符串是'ab'和'cd',我希望获得的输出是:

['abcd', 'acbd', 'acdb', 'cabd', 'cadb', 'cdab']

a总是在b(c之前d)之前看到.我正在努力寻找解决方案.我尝试过如下所示的itertools:

import itertools

def shuffle(s,t):
    string = s+t
    for i in itertools.permutations(string):
        print(''.join(i))

shuffle('ab','cd')

但正如预期的那样,这将返回所有可能的排列,而忽略了a和b(c和d)的顺序.