标签: combinatorics

我面临着一个独特的情况，我的班级有 31 名学生，我希望他们分为 8 组（每组 4 人，其中一组只有 3 名成员）。我试图遵循的具体规则是，如果学生已经一起工作过，那么任何学生都不应与其他学生一起工作。

我需要在三周内创建三个小组集（每次包括 8 组）并遵循这个逻辑。手动操作有点复杂，我希望我可以在 R 中编写代码以获得所需的结果，但是我不知如何纠正以下内容，因为在某些情况下它没有给我写入顺序。

# List of student names
students <- c("Student1", "Student2", "Student3", "Student4", "Student5", "Student6", "Student7", "Student8", "Student9", "Student10",
              "Student11", "Student12", "Student13", "Student14", "Student15", "Student16", "Student17", "Student18", "Student19", "Student20",
              "Student21", "Student22", "Student23", "Student24", "Student25", "Student26", "Student27", "Student28", "Student29", "Student30", "Student31")

# Number of students
num_students <- length(students)

# Number of rounds
num_rounds <- 3

# Group size
group_size <- 4

# Create an empty list to store groups …

这本身不是编程问题,尽管最终目标是设计算法.我正在寻找参考或至少是一种游戏的名称.它在电视游戏节目中非常普遍.游戏如下:

你有许多插槽,每个插槽包含一个你不知道的项目(来自一些有限的集合).你必须猜测每个插槽包含的内容.你告诉你的判断(谁知道每个插槽包含什么),他告诉你有多少猜测是正确的,而不告诉你哪一个.当您成功猜出所有项目时,游戏结束.

我对这种类型的游戏的任何信息感兴趣,包括对尽可能少猜测的算法的参考,等等.这个名字所以我可以google它也没关系.

谢谢!

前段时间我写了一个简单的python程序来强制驱动单个解决方案的驱动器.

alt text http://www.tabbykat.com/Drive%20ya%20Nuts%20Travel%20Sol%20c.jpg

拼图由7个六边形组成,数字为1-6,并且所有部分必须对齐,以便每个数字与下一个部分上的相同数字相邻.

让人不解的具有~1.4G非唯一可能性:你有7!选择的为碎片整理(例如center=0,top=1,继续按顺时针顺序...).在对各个部件进行分类之后,您可以以6种方式旋转每个部件(每个部件是六边形),因此您6**7可以对7个部件的给定排列进行旋转.总计:7!*(6**7)=~1.4G可能性.以下python代码生成以下可能的解决方案:

def rotations(p):
    for i in range(len(p)):
        yield p[i:] + p[:i]

def permutations(l):
    if len(l)<=1:
        yield l
    else:
        for perm in permutations(l[1:]):
            for i in range(len(perm)+1):
                yield perm[:i] + l[0:1] + perm[i:]

def constructs(l):
    for p in permutations(l):
        for c in product(*(rotations(x) for x in p)):
            yield c

但是,请注意,拼图只有~0.2G 唯一可能的解决方案,因为您必须将可能性总数除以6,因为每个可能的解决方案相当于其他5个解决方案(只需将整个拼图旋转1/6圈).

有没有更好的方法来产生这个难题的独特可能性？

我正在阅读,我自己(不是HW)关于编程,一个练习涉及在R中编写Pascal的三角形.我的第一个想法是制作一个列表,然后将其添加到其中,但这并不能很好地工作.然后我想到了从一个向量开始,并在最后制作一个列表.然后我想到制作一个矩阵,并在最后制作一个列表.

不知道哪种方式可以解决这个问题.

任何提示？

谢谢

问题是:

编写一个方法,从大小为n的数组中随机生成一组m个整数.每个元素必须具有相同的被选择概率.

这个答案是否正确？:

我随机选择第一个整数.接下来.如果它已经存在 我不接受别人接受它.并继续,直到我有整数.

让我们定义自定义运算符 - 让它成为++,equals

:- op(900, yfx, equals).
:- op(800, xfy, ++).

事实上:

check(A equals A).

我尝试制作谓词,让它成为check/1,在以下所有情况下都会返回:

check( a ++ b ++ c ++ d equals c ++ d ++ b ++ a ),
check( a ++ b ++ c ++ d equals d ++ a ++ c ++ b),
check( a ++ b ++ c ++ d equals d ++ b ++ c ++ a ),
% and all permutations... of any amount of atoms …

我知道迭代一组大小为n的所有子集是一场性能噩梦,需要花费O(2 ^ n)时间.

如何迭代大小为k的所有子集(对于(0 <= k <= n))？这是一场表演噩梦吗？我知道有(n,k)= n!/ k!(n - k)!可能性.我知道如果k非常接近0或非常接近n,这是一个很小的数字.

在n和k方面,最糟糕的表现是什么？除了O(n!/ k!(n - k)!)之外,还有一种更简单的方式吗？这是渐近地小于O(n!)还是相同？

我需要从另一个包含每种可能组合的列表中创建一个列表.在研究可能的解决方案时,我发现了许多有趣的方法,但所有方法似乎都根据提供的记录数生成结果.我需要组合增加到最大阈值.

即考虑以下数组

1,2,3,4,5

我需要看起来类似的结果(在这个例子中阈值是3)

1
1,2
1,2,3
1,2,4
1,2,5
1,3,4
2,3,5... etc

实际上,数据将是IEnumerable.我用一个简单的int []来说明所需的结果.

我给了n10 ⁵的订单.我要找到一些方法,使用长度步长从地面到达^第 n 步1 or 2 or 3 or.....or m,这里m <= n.

由于答案可能太大,输出模数为10 ⁹ +7.

#include<iostream.h>
using namespace std;

#define ll long long
#define MOD 1000000007

ll countWays_(ll n, ll m){
    ll res[n];
    res[0] = 1; res[1] = 1;
    for (ll i=2; i<n; i++)
    {
       res[i] = 0;
       for (ll j=1; j<=m && j<=i; j++)
         res[i] =(res[i]%MOD+ res[i-j]%MOD)%MOD;
    }
    return res[n-1];
}

ll countWays(ll s, ll m){
    return countWays_(s+1, m);
}
int …

如果在其他地方很容易找到答案,请道歉.我的数学和统计数据很弱,因此我甚至不知道我正在尝试做什么的搜索术语...

我有b我把成匿名区分桶我相同的项目.我想知道所有可能的分布及其概率.例如,如果我有3个桶和3个项目,我想要的答案是:

• [3,0,0] - > 1/9
• [2,1,0] - > 6/9
• [1,1,1] - > 2/9

请注意,桶是匿名的,因此我希望将相同的分布组合起来,如上所述.例如,[2,1,0]案例实际上是[2,1,0],[0,2,1]等案例的总和.

另外,我有最大桶大小的约束.例如,3个球,3个桶,bucketsize = 2应该返回:

• [2,1,0] prob = 7/9
• [1,1,1] prob = 2/9

这可以看到概率树:

Insert item 1 into [0,0,0] -> [1,0,0] p=1  
Insert item 2 into [1,0,0] -> [2,0,0] p=1/3 OR [1,1,0] 2/3  
Insert item 3 into [2,0,0] -> [2,1,0] p=1.0   
Insert item 3 into [1,1,0] -> [2,1,0] p=2/3 OR [1,1,1] p=1/3  

So state [2,1,0] has two paths to it: 1/3*1 AND 2/3*2/3 …