标签: combinatorics

我正在尝试编写一个脚本,该脚本将采用项目字典,每个项目包含0到10之间的值属性,并添加各种元素以选择项目的哪个组合实现所需的总计.我还需要脚本来执行此操作,仅使用具有相同"槽"的项目.

例如:

item_list = {
 'item_1': {'slot': 'top', 'prop_a': 2, 'prop_b': 0, 'prop_c': 2, 'prop_d': 1 },
 'item_2': {'slot': 'top', 'prop_a': 5, 'prop_b': 0, 'prop_c': 1, 'prop_d':-1 },
 'item_3': {'slot': 'top', 'prop_a': 2, 'prop_b': 5, 'prop_c': 2, 'prop_d':-2 },
 'item_4': {'slot': 'mid', 'prop_a': 5, 'prop_b': 5, 'prop_c':-5, 'prop_d': 0 },
 'item_5': {'slot': 'mid', 'prop_a':10, 'prop_b': 0, 'prop_c':-5, 'prop_d': 0 },
 'item_6': {'slot': 'mid', 'prop_a':-5, 'prop_b': 2, 'prop_c': 3, 'prop_d': 5 },
 'item_7': {'slot': 'bot', 'prop_a': 1, 'prop_b': 3, 'prop_c':-4, 'prop_d': …

我试图推导出确定性线性搜索算法的平均案例运行时间.该算法按照A [1],A [2],A [3] ...... A [n]的顺序搜索未排序数组A中的元素x.它在找到元素x时停止或继续直到它到达数组的末尾.我在维基百科上搜索,给出的答案是(n + 1)/(k + 1),其中k是数组中x的存在次数.我以另一种方式接近并得到了不同的答案.任何人都可以给我正确的证据,也让我知道我的方法有什么问题吗？

E(T)= 1*P(1) + 2*P(2) + 3*P(3) ....+ n*P(n) where P(i) is the probability that 
                   the algorithm runs for 'i' time (i.e. compares 'i' elements).
P(i)= (n-i)C(k-1) * (n-k)! / n! 
Here, (n-i)C(k-1) is (n-i) Choose (k-1). As the algorithm has reached the ith 
step, the rest of k-1 x's must be in the last n-i elements. Hence (n-i)C(k-i).
(n-k)! is the total number of ways of arranging …

背景

我参与的一个体育俱乐部向我寻求帮助,为即将到来的比赛提供一些IT支持.

比赛由在比赛日之前不一定知道确切号码的队伍组成.因此需要软件帮助.

所有球队都将在许多比赛中与其他球队见面.因此,匹配的数量是N超过2(2的所有组合),其中N是团队的数量.

我们有不明数量的可用法院来比赛.可能这个数字将是1或可能2,但我想要一个通用的解决方案.

比赛将轮流进行.每回合将在每个球场上进行一场比赛.

例如,如果有两个球场和五个球队(A,B,C,D,E),转弯布局可能如下所示:

Turn      Court 1     Court 2
--------------------------------
 1        A vs B      C vs D
 2        A vs C      D vs E
 3        A vs D      B vs E
 4        B vs D      C vs E
 5        A vs E      B vs C

问题

因此,我的问题是找到一个生成一组符合以下简单规则的转弯的算法:

1. 所有球队必须在比赛期间恰好与其他所有球队会面一次.
2. 一支球队不能在同一回合打两场比赛(即在法院1和2上不能同时比赛)
3. 特定球队的转变应该在整个比赛中展开.

规则3详细说明

规则1和2非常简单,我已经有了解决方案.规则3给了我一些问题.我会尝试展示它的含义:

假设我有5支球队(如上所述),但只有1支球队.超过10回合有10场比赛.一种可能的布局是

Turn   Court 1
 1 …

假设我有10个盒子和4种不同类型的彩球:​​黑色,蓝色,红色,绿色.我想在10个盒子中以大致相等的比例分配不同颜色的球.例如,一个可接受的解决方案是在10个盒子中放置2个黑色,2个蓝色,3个红色和3个绿色球.

现在,更具体地说,假设我有10个UIImageViews,以及可变数量的UIImages(Facebook,Twitter,Flickr等)放入这些UIImageViews中.如果我允许用​​户关闭某种类型,则可以有可变数量的类型(全部三种,只有两种,只有一种等).是否有一种有效的算法将可变数量的对象分配到静态数量的框中？

我能想到的最直接的方式,但我觉得它非常低效,就是有一个for循环,只需将每种类型的球(UIImage)的数量增加到一个盒子(UIImageView)中,直到球的总数为止等于盒子的数量.有没有更好的办法？

这个问题与SO帖子几乎相同,只是我正在寻找一个VB.NET(.NET 4)解决方案.我已经足够长时间旋转我的车轮,试图想出一个解决这个"动力装置"问题的通用解决方案.

鉴于:

Dim choices As IEnumerable(Of String) = {"Coffee", "Tea", "Milk", "Cookies"}
Dim choiceSets = choices.CombineAll()

我正在寻找choiceSets一个IEnumerable(Of IEnumerable(Of T))能做以下事情的事情:

For each choiceSet in choiceSets
    Console.WriteLine(String.Join(", ", choiceSet))
Next

并获得如下结果:

Coffee
Tea
Milk
Cookies
Coffee, Tea
Coffee, Milk
Coffee, Cookies
Tea, Milk
Tea, Cookies
Milk, Cookies
Coffee, Tea, Milk
Coffee, Tea, Cookies
Coffee, Milk, Cookies
Tea, Milk, Cookies
Coffee, Tea, Milk, Cookies

正如你所看到的,这是每一个不重复的从源的组合IEnumerable(Of T)(其中可能有1到很多条-这个例子中只有4),它的运行基于源项目的顺序IEnumerable(Of T),并在每个项目列表是> =内部项目数量的上一项IEnumerable(Of T) …

我希望生成除空集之外的集合的所有子集

即

(all-subsets #{1 2 3}) => #{#{1},#{2},#{3},#{1,2},#{2,3},#{3,1},#{1,2,3}}

怎么能在clojure中完成？

我正在寻找R一个函数partial.sum(),它接受一个数字向量并返回所有部分和的升序排序向量:

test=c(2,5,10)
partial.sum(test)

# 2 5 7 10 12 15 17
## 2 is the sum of element 2
## 5 is the sum of element 5    
## 7 is the sum of elements 2 & 5    
## 10 is the sum of element 10    
## 12 is the sum of elements 2 & 10    
## 15 is the sum of elements 5 & 10
## 17 is the sum of elements 2 & 5 & …

我正在努力在JavaScript中实现一个subfactorial函数来计算n元素可能的紊乱总数,而我似乎搞砸了一些东西.我的计算似乎总是一个高,或一个低.我搞砸了什么？这是一个舍入错误吗？

function subfactorial (x) {
  x = parseInt(x);
  var i;
  var sub = 0;
  var sum = 0;
  sum += factorial(x);
  for (i = 0; i < x; i++) {
    sub += (Math.pow(-1, i)/factorial(i));
  }
  return sum * sub;
}

function factorial (y) {
  var negative = y < 0;
  y = parseInt(Math.abs(y)); // Ints only
  var acc = 1;
  for (y; y > 0; y--) {
    acc *= y;
  }
  return negative ? -acc : acc;
} …

背景:

我有44906项清单:large = [1, 60, 17, ...].我还有一台内存有限的个人电脑(8GB),运行Ubuntu 14.04.4 LTS.

目标:

我需要以large内存效率的方式找到所有成对组合,而不事先填充所有组合的列表.

问题和我到目前为止所做的:

当我使用itertools.combinations(large, 2)并尝试将其分配到列表时,我的内存会立即填满,而且性能会非常慢.这样做的原因是,两两组合的数量是这样n*(n-1)/2,其中n是列表中元素的个数.

n=44906出来的组合数量44906*44905/2 = 1008251965.包含这么多条目的列表太大而无法存储在内存中.我希望能够设计一个函数,以便我可以插入一个数字i来查找i此列表中数字的成对组合,以及以某种方式动态计算此组合的方法,而无需参考1008251965元素列表不可能存储在内存中.

我正在尝试做的一个例子:

假设我有一个数组 small = [1,2,3,4,5]

在我有代码的配置中,itertools.combinations(small, 2)将返回一个元组列表:

[(1, 2), # 1st entry
 (1, 3), # 2nd entry
 (1, 4), # 3rd entry
 (1, 5), # 4th entry
 (2, 3), # 5th entry
 (2, 4), # 6th entry 
 (2, 5), # 7th entry
 (3, 4), …

我正在尝试计算itertools.product()的第n个结果

test = list(product('01', repeat=3))
print(test)

desired_output = test[0]
print(desired_output)

所以不要得到:

[('0', '0', '0'), ('0', '0', '1'), ('0', '1', '0'), ('0', '1', '1'), ('1', '0', '0'), ('1', '0', '1'), ('1', '1', '0'), ('1', '1', '1')]

我想要:

('0', '0', '0')

然而,正如您可能已经猜到的那样,它不能很好地扩展.这就是为什么我只想计算第n个值.

我阅读了 Nth Combination,但我需要product()提供的重复功能

提前致谢!