标签: combinatorics

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

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

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

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

问题

我有一群人,我希望每个人与小组中的其他人进行1:1的会面.给定的人一次只能与另一个人见面,所以我想做以下事情:

1. 找到所有可能的配对组合
2. 组合在一起成为"轮次"会议,其中每个人只能进行一次轮次,并且轮次应包含尽可能多的对,以满足最少轮次中的所有可能的配对组合.

为了说明所需输入/输出方面的问题,假设我有以下列表:

>>> people = ['Dave', 'Mary', 'Susan', 'John']

我想生成以下输出:

>>> for round in make_rounds(people):
>>>     print(round)
[('Dave', 'Mary'), ('Susan', 'John')]
[('Dave', 'Susan'), ('Mary', 'John')]
[('Dave', 'John'), ('Mary', 'Susan')]

如果我有一个奇数的人,那么我会期待这个结果:

>>> people = ['Dave', 'Mary', 'Susan']
>>> for round in make_rounds(people):
>>>     print(round)
[('Dave', 'Mary')]
[('Dave', 'Susan')]
[('Mary', 'Susan')]

这个问题的关键是我需要我的解决方案(在合理范围内).我已经写了代码工作,但随着规模people的增长变得缓慢呈指数.我不太了解编写高性能算法来了解我的代码是否效率低下,或者我是否只是受问题参数的约束

我试过的

第1步很简单:我可以使用itertools.combinations以下方法获得所有可能的配对:

>>> from itertools import combinations
>>> people_pairs = set(combinations(people, 2))
>>> print(people_pairs)
{('Dave', 'Mary'), ('Dave', 'Susan'), ('Dave', 'John'), ('Mary', …

编辑:对不起,但我忘了提到我需要计数器变量的值.所以制作一个循环并不是我害怕的解决方案.

我不确定这是否可行,但我想做以下事情.对于函数,传递数字数组.每个数字都是for循环的上限,例如,如果数组是[2, 3, 5],则应执行以下代码:

for(var a = 0; a < 2; a++) {
     for(var b = 0; b < 3; b++) {
          for(var c = 0; c < 5; c++) {
                doSomething([a, b, c]);
          }
     }
}

因此,嵌套for循环的数量等于数组的长度.有没有办法让这项工作？我正在考虑创建一段代码,将每个for循环添加到一个字符串,然后通过它进行评估eval.然而,我已经阅读过,这eval不应该是一个人的首选,因为它也会产生危险的结果.

这里适合哪种技术？

有人能为我提供一个函数的链接或伪代码,用于查找n中k个元素的所有组合吗？可能在STL.我不需要计算n选择k,我需要列出所有大小为k的数字向量.

谢谢

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

给你一个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 …

查找字符串的所有排列是通过众所周知的Steinhaus-Johnson-Trotter算法.但如果字符串包含重复的字符,如
AABB,
那么可能的唯一组合将是4!/(2!*2!)= 6

实现这一目标的一种方法是我们可以将它存储在数组中,然后删除重复项.

有没有更简单的方法来修改约翰逊算法,因此我们永远不会生成重复的排列.(以最有效的方式)

或者旅行推销员扮演魔术!

我认为这是一个相当有趣的算法挑战.好奇,如果有人有任何好的解决方案的建议,或者它已经以已知的方式解决.

TCGPlayer.com为各种游戏销售收藏卡,包括Magic the Gathering.它们实际上是来自多个供应商(50+)的转售商,而不仅仅是从他们的库存中销售卡片.每个供应商都有不同的卡片库存和每张卡的不同价格.每个供应商也收取统一运费(通常).鉴于所有这些,如何找到一副牌的最佳价格(比如说40到100张牌)？

只是找到每张卡的最优价格是行不通的,因为如果您从10个不同的供应商订购10张卡,那么您支付10次运费,但如果您从一个供应商订购所有10个卡,则只支付一次运费.

另一天晚上,我写了一个简单的HTML Scraper(使用HTML Agility Pack),它可以获取每张卡的所有不同价格,然后找到所有带有卡中所有卡的供应商,总计来自每个供应商的卡的价格和按价格排序.这真的很容易.总价格最终接近所有卡的总中位数价格.

我注意到一些个人卡最终远高于中位数价格.这引发了在多个供应商之间拆分订单的问题,但只有通过将订单拆分以支付额外运费(每个添加的供应商增加另一个运费)才能节省足够的成本.

从逻辑上看,似乎最好的价格可能只涉及一些不同的供应商,但如果这些卡足够昂贵(有些是),那么理论上从不同的供应商订购每张卡仍然可以节省足够的成本以证明所有额外的运费.

如果你打算解决这个问题,你会怎么做？纯粹的蛮力计算卡/供应商组合的每种可能组合？在我的生命中更有可能完成的过程似乎涉及在固定次数的迭代中的一系列有条理的估计.我有几个想法,但我很好奇其他人的建议.

我正在寻找比实际代码更多的算法.我目前正在使用.NET,如果这有任何区别.

我是一名高中计算机科学专业的学生,​​今天我遇到了一个问题:

节目描述:骰子玩家有一种信念,即投掷三个骰子十分比一个骰子更容易获得.你能写一个证明或反驳这种信念的程序吗？

让计算机计算所有可能的方式可以抛出三个骰子:1 + 1 + 1,1 + 1 + 2,1 + 1 + 3等.将这些可能性加起来,看看有多少给出九个结果,多少给十.如果更多给十,那么信念就会得到证实.

我很快就制定了一个强力解决方案

int sum,tens,nines;
    tens=nines=0;

    for(int i=1;i<=6;i++){
        for(int j=1;j<=6;j++){
            for(int k=1;k<=6;k++){
                sum=i+j+k;
                //Ternary operators are fun!
                tens+=((sum==10)?1:0);
                nines+=((sum==9)?1:0);
            }
        }

    }
    System.out.println("There are "+tens+" ways to roll a 10");
    System.out.println("There are "+nines+" ways to roll a 9");

哪个工作得很好,蛮力解决方案就是老师要我们做的事情.但是,它不适合,我试图找到一种方法,使算法可以计算的方式来推出数Ñ骰子得到一个具体的数字.因此,我开始生成用n个骰子获得每个总和的方法的数量.使用1个模具,每个模具显然有1个解决方案.然后我通过蛮力计算了2和3个骰子的组合.这些是两个:

有1种方法可以滚动2种
有2种方式可以滚动3种
有3种方式可以滚动4种
有4种方式可以滚动5种
有5种方式可以滚动6种
有6种方式可以滚动7种
有5种滚动方式8滚动方式
有4种方式滚动方式
有3种方式
有2种滚动方式有11
种滚动方式有1种方式

这看起来很简单; 它可以用简单的线性绝对值函数计算.但事情变得越来越棘手.有3:

有1种方法可以滚动3种
有3种方式可以滚动4种
有6种方式可以滚动5种
有10种方式可以滚动6种
有15种方式可以滚动7种
有21种方式可以滚动8
种滚动的25种方式9
有27种方式滚动10
种滚动方式有27种方式
有25种方式滚动12
种滚动方式有21种方式有13 …

我们有两个列表,A和B:

A = ['a','b','c']
B = [1, 2]

是否有一种pythonic方法来构建包含2 ^ n的A和B之间的所有映射集(此处为2 ^ 3 = 8)？那是:

[(a,1), (b,1), (c,1)]
[(a,1), (b,1), (c,2)]
[(a,1), (b,2), (c,1)]
[(a,1), (b,2), (c,2)]
[(a,2), (b,1), (c,1)]
[(a,2), (b,1), (c,2)]
[(a,2), (b,2), (c,1)]
[(a,2), (b,2), (c,2)]

使用itertools.product,可以获得所有元组:

import itertools as it
P = it.product(A, B)
[p for p in P]

这使:

Out[3]: [('a', 1), ('a', 2), ('b', 1), ('b', 2), ('c', 1), ('c', 2)]

我试图找到一个函数来置换向量的所有唯一排列,同时不计算相同元素类型的子集内的并置.例如:

dat <- c(1,0,3,4,1,0,0,3,0,4)

具有

factorial(10)
> 3628800

可能的排列,但仅限于 10!/(2!*2!*4!*2!)

factorial(10)/(factorial(2)*factorial(2)*factorial(2)*factorial(4))
> 18900

忽略同一元素类型的子集内的并置时的唯一排列.

我可以通过使用unique()和permn()包中的函数来获得这个combinat

unique( permn(dat) )

但这在计算上非常昂贵,因为它涉及枚举n!,这可能比我需要的排列多一个数量级.没有先计算,有没有办法做到这一点n!？