标签: combinatorics

由于赋值问题可以以单个矩阵的形式提出,如果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 …

出于特殊的原因,我决定寻找一种算法,该算法产生1 ... n之间k个整数的所有可能选择,其中k整数中的顺序无关紧要(n选择k thingy).

从完全相同的原因,这是没有理由的,我也用C#实现了它.我的问题是:

你在我的算法或代码中看到任何错误吗？而且,更重要的是,你能建议一个更好的算法吗？

请注意算法而不是代码本身.这不是我写过的最漂亮的代码,虽然可以告诉你是否看到了错误.

编辑: Alogirthm解释 -

• 我们持有k指数.
• 这会创建k个嵌套for循环,其中循环i的索引是indices [i].
• 它模拟k for for循环,其中indices [i + 1]属于嵌套在indices [i]循环中的循环.
• indices [i]从索引[i-1] + 1到n-k + i + 1运行.

码:

public class AllPossibleCombination
{
    int n, k;
    int[] indices;
    List<int[]> combinations = null;

    public AllPossibleCombination(int n_, int k_)
    {
        if (n_ <= 0)
        {
            throw new ArgumentException("n_ must be in N+");
        }
        if (k_ <= 0)
        {
            throw new ArgumentException("k_ must be in N+");
        }
        if (k_ …

我最近面临一个编程算法的提示,我不知道该怎么做.我以前从来没有真正写过算法,所以我对此有点新意.

问题是写一个程序,以确定收银员根据硬币值和硬币数量作为变化回馈所有可能的硬币组合.例如,可能有一个有4个硬币的货币:2美分,6美分,10美分和15美分硬币.这有多少组合等于50美分？

我正在使用的语言是C++,虽然这并不重要.

编辑:这是一个更具体的编程问题,但我如何分析C++中的字符串来获取硬币值？它们是在文本文档中给出的

4 2 6 10 15 50 

(在这种情况下,数字对应于我给出的例子)

如何计算大n和和的二项式系数模数142857 r.142857有什么特别之处吗？如果问题是模数p在哪里p是素数那么我们可以使用卢卡斯定理但是应该为142857做什么.

假设我们有n投掷k球的垃圾箱.什么是快速(即使用numpy/scipy而不是python代码)方式来生成所有可能的结果作为矩阵？

例如,如果n = 4和k = 3,我们需要以下内容numpy.array:

3 0 0 0
2 1 0 0
2 0 1 0
2 0 0 1
1 2 0 0
1 1 1 0
1 1 0 1
1 0 2 0
1 0 1 1
1 0 0 2
0 3 0 0
0 2 1 0
0 2 0 1
0 1 2 0
0 1 1 1
0 1 …

给定二进制矩阵(值为0或1),相邻的1表示"丘陵".另外,给定一些数字k,找到你需要"翻转"为1的最小数量0,以便形成至少大小的山丘k.

编辑:为了澄清,相邻意味着左右上下社区.对角线也不能算作相邻.例如,

[0 1 0 1]

是一个2号山,

[0 1 1 0]

定义2个大小为1的山丘,

[0 1 1 1]

定义1个大小为3的小山,和

[1 1 1 1]

定义1个4号山.

同样为了澄清,尺寸由相邻的1的斑点形成的区域定义.

我的初始解决方案涉及将每个现有的山变换为图的节点,并将成本作为到达每个其他节点的最小路径.然后,执行DFS(或类似算法)以找到最低成本.

如果选择某条路径可以降低另一条边的成本,那么就会失败,而解决这个问题的解决方案(我能想到的)与蛮力解决方案太接近了.

假设您有 n 个排序的数字数组，您需要从每个数组中选择一个数字，以使 n 个所选元素之间的最小距离最大化。

例子：

arrays:
[0, 500]
[100, 350]
[200]

2<=n<=10每个数组都可以有~10^3-10^4元素。

在此示例中，最大化最小距离的最佳解决方案是选择数字：500、350、200 或 0、200、350，其中最小距离为 150，并且是每个组合的最大可能值。

我正在寻找一种算法来解决这个问题。我知道我可以对最大最小距离进行二分搜索，但我不知道如何确定是否存在最大最小距离至少为 d 的解决方案，以便二分搜索起作用。我在想动态编程可能会有所帮助，但还没有找到 dp 的解决方案。

当然，用 n 个元素生成所有组合效率不高。我已经尝试过回溯，但速度很慢，因为它尝试了每种组合。