标签: combinatorics

主要目标：

创建一个 JavaScript 函数，帮助每个战士有更好的战斗顺序。一些拳手在整个比赛中有七次参赛。在fighter1和fighter2列中，在给定的数据中，您可以看到每个战士的战斗编号。每个同名战士的差距太近或太远。我们的目标是：

1. 每个同名战士的差距应该有10到30个战斗编号差异。10 是最小间隙，30 是最大间隙。
2. `fightNumber 应该是唯一的，范围仅在 1 到 162 之间。（战斗编号不能重复）

对象数据：

1. id=战斗id
2. 战斗机1和战斗机2 =这些是将要匹配的战斗机。战斗机 1 与战斗机 2 - 战斗机有不同的名称。每个可能的名称都在战斗机 1 或战斗机 2 中
3. FightNumber - 这是每场战斗的唯一序列号。一旦产生新的序列就可以更新（范围是从1到条目数据的总长度（本次测试我打了162场））

创建该函数的目的：

这将帮助每个战士不要等待太久或太短，我们需要给予间隙 10 - 30 战斗编号差异。

我的目标例如是：

战斗机 1：“V”是 FightNumber 1。它的下一场战斗应该是10（最小） 或 30（最大）。但在我当前的函数中，它在 FightNumber 6 处再次匹配 （仅等于 5 FightNumber 差异）。

这意味着我当前的函数不满足我的条件，即等于（请参阅上述条件）。

我认为我的身体状况有问题。有没有办法可以实现我的目标？

  const data = [
    { id: "1", fighter1: "V", fighter2: "DD", fightNumber: 1 },
    { id: "2", fighter1: "R", …

如果每个单词以随机辅音开头,并且在元音和辅音交替之后,我可以从英语小写字母中生成多少长度为6的单词？

如果我在字母表中添加数字怎么办？

另见这个问题.

考虑计算结构上不同的二叉搜索树的数量的问题:

给定N,找到包含值1 ... N的结构上不同的二叉搜索树的数量

给出一个解决这个问题的算法很容易:修复根中的每个可能的数字,然后递归地解决左右子树的问题:

countBST(numKeys)
    if numKeys <= 1
        return 1
    else
        result = 0
        for i = 1 .. numKeys
            leftBST = countBST(i - 1)
            rightBST = countBST(numKeys - i)

            result += leftBST * rightBST

        return result

我最近熟悉了treaps,我给自己提出了以下问题:

给定N,找到包含值1 ... N的不同treap的数量,优先级为1 .. N.如果它们在相对于密钥或优先级的结构上不同,则两个treap是不同的(请继续阅读以进行说明).

我一直试图找出一个可以解决这个问题的公式或算法,但我还没有成功.这是我注意到的:

1. 对于这些问题的答案n = 2,并n = 3似乎是2和6,基于我在纸上画树木.
2. 如果我们忽略了表示treaps的部分也可能与节点的优先级不同,那么问题似乎与仅计算二进制搜索树相同,因为我们将能够为每个BST分配优先级,以便它也尊重堆不变量.我没有证明这一点.

3. 我认为困难的部分是考虑到在不改变结构的情况下置换优先级的可能性.例如,考虑这个treap,其中节点表示为(key, priority)对:

             (3, 5)
             /    \ 
        (2, 3)    (4, 4)
        /              \
   (1, 1) …

   Run Code Online (Sandbox Code Playgroud)

假设我有大理石,每种都可以是8种颜色中的一种.我想迭代所有可能的大理石颜色组合值.我怎样才能在MatLab中做到这一点？

例如,如果n = 2,那么我想迭代:

2 0 0 0 0 0 0 0

1 1 0 0 0 0 0 0

1 0 1 0 0 0 0 0

1 0 0 1 0 0 0 0

1 0 0 0 1 0 0 0

1 0 0 0 0 1 0 0

1 0 0 0 0 0 1 0

1 0 0 0 0 0 0 1

0 2 0 0 0 0 0 0

0 1 1 0 …

假设我有一组有限的大小为n的数值.

问题:是否有一种有效的算法来枚举该组的k-组合,以便组合I在组合J之前,如果I中元素的总和小于或等于J中元素的总和？

显然,可以简单地枚举组合并根据它们的总和对它们进行排序.但是,如果集合很大,那么所有组合的粗略枚举,更不用说排序,将是不可行的.如果我只对获得按总和排序的第一个m <<选择(n,k)组合感兴趣,是否有可能在宇宙热死之前获得它们？

我的侄子有一项新业务,将商界人士聚在一起喝咖啡和谈话.这有点像音乐椅.经过一段时间后,每个人都会起床到另一张桌子.这个想法是每个人都有机会与每个人交谈.他试图弄清楚如何用16个人和4个桌子来做,每个人都移动5次.

我想找出一个算法来做到这一点,但我发现这个问题比我想象的要困难得多.为了简化它,我研究了如何用6个人和3个表做到这一点.它可以表示如下:

Step 1: (1, 2), (3, 4), (5, 6)
Step 2: (1, 3), (2, 5), (4, 6)
Step 3: (1, 4), (2, 6), (3, 5)
Step 4: (1, 5), (2, 4), (3, 6)
Step 5: (1, 6), (2, 3), (4, 5)

一种不太有效的可能性是产生所有可能的组合并消除任何相互排斥的组合.然而,奇怪的组合,这是不可能的.例如,如果有6个人只有2个桌子,那么将有两个人不止一次坐在同一张桌子上.当然,算法的想法是让每个人在最短的步骤中至少相遇一次.

我需要在N阶直接无环图上找到拓扑排序的最大数量.我通过在各种直接非循环图上运行深度优先搜索算法进行检查,看起来它是在图上运行DFS后创建的深度优先搜索算法林的大小.或许我完全错了或错过了什么.我还需要证明一下.任何帮助将不胜感激.谢谢.

我希望获得列表的所有排列,但无需重复,无论是否排序.这很难描述,所以我举一个例子.我真的很想知道这个操作的名称,因为我一直都在使用它.另外一个在python中实现这个的简单方法真的可以帮到我.谢谢!

例如

['foo', 'bar', 'la']

==>

['foo', 'bar']
['foo', 'la']
['ba', 'la']

给定一个偶数个单元格的网格,其中网格边缘上的两个单元格缺失,我想形成成对的相邻单元格,使得没有合作伙伴没有剩余单元格(不计算"缺失"单元格) .

根据放置两个"缺失"单元的位置,我相信它总是可能或总是不可能做出这样的安排.我在这里画了两个例子,左边的绘图是成功的尝试,右边的绘图是不成功的尝试(两个单元格没有合作伙伴).为摇摇欲坠的相机手道歉.

单元格内的箭头表示该单元与哪个邻居合作.

我有两个问题:

1. 我怎么知道放置"缺失"细胞的安全位置,而不是让每个细胞都成为伴侣？

2. 在给定上面提到的条件的情况下,创建这样的排列的算法会是什么样的,并且还假设单元格表可以更大(尽管总是具有偶数个单元格)并且不一定是正方形(但是矩形)？示例可以是3x4网格或6x6网格.

我还不知道如何知道放置"缺失"单元的安全位置,但只要它们处于已知安全的位置,我的算法如下:

1. For each cell that isn't "missing" or already paired, iterating from top-left to bottom right, horizontally first:
2. Choose a random neighbor to form a pair with: either right or bottom.
3. Check all the cells to see if there are any cells that cannot make a pair, if so:
4. Undo the last pair, go back to 2 and choose the other neighbor.

我完全不知道图论或其他什么可以帮助我找到一个好的解决方案,所以我非常感谢你能给予的任何帮助.任何非超级晦涩的语言中的伪代码或真实代码都会很棒,简单的文本解释也是如此.

如果X是一组数字,然后?X是一个多集的数字,表示每个2号之间的成对减法.例如,如果X一行中的一组点按递增顺序排列,那么?X这些点之间的成对距离是多重的.如何编写一个返回数字列表的成对距离的函数？以下工作,但我想要一个更优雅的解决方案.请包括理论或直觉,如果可能的话,可以提供有关如何解决类似问题的见解.

pairwise_distances :: [Int] -> [Int]
pairwise_distances [] = []
pairwise_distances [x] = []
pairwise_distances (x:xs) = sort $ map (abs . (x-)) xs ++ pairwise_distances xs

pairwise_distances [3,2,1] -- [1,1,2]
pairwise_distances [0,2,4,7,10] -- [2,2,3,3,4,5,6,7,8,10]