标签: combinatorics

感觉这应该很简单，但我已经经历过堆栈溢出和combn帮助，但看不到解决方案。

下面的玩家需要组成 3 对 2 的队伍。我需要找到所有可能的队伍组合。例如，两个可能的团队是“Ross”、“Bobby”和“Casper”在一个团队中，“Max”和“Jake”在另一团队中。我该如何编码？

players <- c("Ross", "Bobby", "Max", "Casper", "Jake")

(在任何人问之前,这不是功课.)

假设你有2个阵列y0和y1哪里

y0 = [1,2,3,4,5,6] 和 y1 = [2,1,6,3,4,5]

注意y0[0] = y1[1] = 1,它本质上意味着y0[0]连接到y1[1].同样,y0[2] = y1[3] = 3它们也是"连接"的.

(图片提供:belisarius)

一个数组中的每个元素在第二个数组中都有一个对应的条目.想象一下,数组中的每个元素都是一个顶点,这些连接就像边缘从一个数组绘制到另一个数组.

我需要找到一组边(最大尺寸),这样"边"(或线)都不会相交.

在上面的例子中,请注意,

1. Edge 1和Edge 2相交.
2. Edge 6 将与...相交 Edge 3, Edge 4, Edge 5.

因此,解决方案可以是1,3,4,5或2,3,4,5(大小= 4),因为这些线中没有一条将彼此相交.可以有多种解决方案,但我只需要一种.

我的问题,是否有类似于此的已知CS问题？我应该使用什么算法？

我试图用一个例子来解释我的问题,但是,如果它仍然不清楚我会澄清任何疑问.提前致谢.

我正在寻找一种有效的算法来计算任何给定整数的乘法分区.例如,12的这种分区的数量是4,即

12 = 12×1 = 4×3 = 2×2×3 = 2×6

我已经阅读了维基百科文章,但这并没有真正给我一个生成分区的算法(它只讨论了这些分区的数量,说实话,即使这对我来说也不是很清楚!) .

我正在看的问题要求我为非常大的数字(> 10亿)计算乘法分区,所以我试图为它提出一种动态编程方法(以便找到所有可能的分区,用于较小的数字可以是当较小的数字本身是一个较大数字的因素时重复使用),但到目前为止,我不知道从哪里开始!

任何想法/提示将不胜感激 - 这不是一个家庭作业问题,只是我试图解决的问题,因为它看起来很有趣!

我已经工作了几个小时,但无法弄明白.

将排列度定义为创建它时需要组合的最小转置数.所以程度(0, 1, 2, 3)为0,程度(0, 1, 3, 2)为1,程度(1, 0, 3, 2)为2,等等.

将空间Snd看作n具有度数的长度序列的所有排列的空间d.

我想要两种算法.一个在该空间中进行置换并为其分配索引号的另一个,并且另一个取一个项的索引号Snd并检索其置换.索引号显然应该是连续的(即在范围内0 to len(Snd)-1,每个排列具有不同的索引号.)

我希望这样实现O(sane); 这意味着如果你要求排列数17,算法不应该遍历0到16之间的所有排列来检索你的排列.

不知道怎么解决这个问题？

(如果你要包含代码,我更喜欢Python,谢谢.)

更新:

我想要一个解决方案

1. 排列是根据它们的词典顺序排序的(而不是通过手动排序它们,而是通过一个有效的算法来给它们开始的词典顺序)和
2. 我希望算法也接受不同程度的序列,所以我可以说"我希望在范围(5)的置换空间中的所有1或3或4级排列中排列数为78".(基本上函数会取一个度数元组.)这也会影响从排列计算索引的反函数; 根据度数集,指数会有所不同.

我过去两天试过解决这个问题而且我没有成功.如果你能提供Python代码,那就是最好的.

我正在研究一个问题,我期望N<20在XOR等于的数组中找到元素组合的数量P.

例如:我们的数组是{2 4 5 2 7}

1)如果N = 2且P = 6,

答案是2(因为我们只能选择(2 xor 4)= 6和(4 xor 2)= 6)

{ 2 4 5 2 7}或{2 4 5 2 7}

2)如果N = 3且P = 6

答案是1((4 x或5 x或7)= 6)

数组的大小可能非常大(大约10 ^ 6)所以我正在寻找快速算法来解决这个问题.

由于赋值问题可以以单个矩阵的形式提出,如果numpy具有解决这种矩阵的函数,我就会徘徊.到目前为止,我没有找到.也许你们其中一个人知道numpy/scipy是否有一个赋值问题解决函数？

编辑:同时我在http://www.clapper.org/software/python/munkres/找到了一个python(不是numpy/scipy)实现.我仍然认为numpy/scipy实现可能会快得多,对吧？

我知道有一种算法允许,在给定数字组合(无重复,无顺序)的情况下,计算字典顺序的索引.
对我的应用来说,加速事情会非常有用......

例如:

combination(10, 5)  
1 - 1 2 3 4 5  
2 - 1 2 3 4 6  
3 - 1 2 3 4 7  
....  
251 - 5 7 8 9 10  
252 - 6 7 8 9 10  

我需要算法返回给定组合的索引.
es:index( 2, 5, 7, 8, 10 )- > index

编辑:实际上我正在使用一个生成所有组合C(53,5)的Java应用程序并将它们插入到TreeMap中.我的想法是创建一个包含我可以使用此算法索引的所有组合(和相关数据)的数组.
一切都是加速组合搜索.但是我尝试了一些(不是全部)解决方案,你提出的算法比TreeMap中的get()慢.
如果它有帮助:我的需求是从0到52的5到53的组合.

再次感谢大家:-)

我正在寻找一种算法来为一组团队生成一个时间表.例如,想象一个体育赛季,每个球队互相比赛,一次作为主队,另一个作为另一支球队的球队.

要在赛季中生成一组所有游戏很容易,如果团队是以下团队的列表:

set((x, y) for x in teams for y in teams if x != y)

但是我也希望按照时间顺序对游戏进行排序,使其满足有效游戏时间表的约束并且看起来"自然随机".

约束条件是游戏列表应该可分组为多轮,其中每轮包含n/2个游戏(其中n是团队数量),其中每个团队与另一个团队配对.

为了使赛程看起来更自然,两队不应连续两轮面对对方.也就是说,如果(a,b)在一轮中进行,则游戏(b,a)不应该在分机中进行.

此外,每支球队应尽可能多地作为客场球队和其他球队作为主队进行比赛.我认为不可能总是满足这个约束,所以拥有它更好.例如,一支球队不应该打8场主场比赛,然后打8场客场比赛.

以下是我现在得到的.该算法的主要问题是它经常陷入while循环.特别是当团队数量为16或更多时.它也是非常低效的,因为它建立在使用随机样本函数并希望得到正确的基础上:

from random import sample
def season_schedule_order(teams, pairs):
    n_games_per_round = len(teams) // 2
    last_pairs = set()
    while pairs:
        r_pairs = set(sample(pairs, n_games_per_round))
        # Check that each team is present once in the round.
        r_teams = set(x for (x, y) in r_pairs) | set(y for (x, y) in r_pairs)
        if r_teams != teams:
            continue
        # Check that two teams doesn't face …

我希望能够获取一系列数字并返回包含三元组的列表而不重复.x的每个元素应该在三元组的每个位置出现一次.目标是获得如下内容:

get_combinations_without_duplicates(3) = [(0, 1, 2), (1, 2, 0), (2, 0, 1)]

对于范围(3),这只是一个列表旋转,但对于更高的范围,有更多可能的组合.我希望能够随机生成满足这些约束的三元组列表.

假设我们首先为n = 4的情况指定每个三元组的第一个元素:

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

第一个三元组的第二个元素可以是除0之外的任何元素.一旦选择了其中一个元素,那么这将限制下一个三元组的选项,依此类推.目标是使用一个函数来获取数字并以这种方式创建三元组,但并不总是创建相同的三元组.也就是说,最终结果可能是轮换:

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

要么

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

这是这个函数的一个实现:

def get_combinations_without_duplicates(n):
    output = []
    second = range(n)
     third = range(n)
for i in range(n):
    triple = [i]
    #Get the second value of the triple, but make sure that it isn't a 
    #duplicate of the first …

我遇到了一个有趣的编程问题,我似乎无法制定解决方案.假设你有N种不同颜色的K球.您必须将所有球分成尽可能多的组,这样两个组就不会相同.(如果每组颜色的球数相同,则认为两组相同.)您可以制作的最大组数是多少？

约束:1 <= K <= 50,1 <= N <= 14

澄清:我们想要一个算法,它接受一个整数数组> = 1.数组的大小为N,它包含的值之和为K.算法应返回最大组数.

关于这个问题的算法方法的任何想法？