问题标签 [combinations]

我正在尝试编写一个算法来计算结果。但我需要组合数学方面的帮助。

假设我必须从 1 到 10 中选择 2 个数字。根据计数的基本规则，在没有任何限制的情况下，可能结果的数量是 10 * 10 = 100。（选择第一个数字的 10 个可能结果 x 10 个可能选择第二个的结果）。

鉴于第一个数字必须大于第二个数字，可能的结果数量是多少？

我有一些代码来计算排列和组合，并且我正在努力让它更好地适用于大量数字。

我找到了一种更好的排列算法，可以避免大的中间结果，但我仍然认为我可以在组合方面做得更好。

到目前为止，我已经放入了一个特殊情况来反映 nCr 的对称性，但我仍然想找到一个更好的算法来避免调用 factorial(r)，这是一个不必要的大中间结果。如果没有这种优化，最后一个 doctest 会花费很长时间来计算阶乘（99000）。

任何人都可以提出一种更有效的计算组合的方法吗？

我正在寻找类似于Path.Combine方法的东西，可以帮助我正确组合绝对路径和相对路径。例如，我想要

屈服c:\alpha\gamma而不是c:\alpha\..\gamma像Path.Combine那样屈服。有什么简单的方法可以做到这一点吗？不用说，我还想对.路径或多条..路径（例如..\..\）进行循环以正常工作。

我将完成我作为编码员的学徒期，并且我有一个不错的 j2me 项目要处理，但我不得不承认我对数学算法的了解并不如我所愿。

我的问题是从一组给定的值创建所有可能的“多米诺骨牌对”。例如：可能的值从 0 到 6。现在想象一些具有这些值的多米诺标记。输出应该是这样的：

00
01
02
03
04
05
06
11
12
13
...

每对只出现一次，但具有两个相等值的对是可能的。

我已经搜索过这个问题，但要么我没有找到这个特定问题的解决方案，要么我并不真正了解算法是如何工作的。

我真的很感激任何解释和算法。也可以随意发布替代解决方案。我不仅希望有一个解决方案，而且还要理解它；）

我有收藏List<Car>。

如何将此集合中的每个项目与其余项目进行比较而不重复。

前任：

1. 迭代：

这辆车是奥迪，第二辆车是宝马

这是不允许的：

n 次迭代

这辆车是宝马，第二辆车是奥迪

更清晰：

我只是不想比较汽车两次（你知道第一次迭代比较汽车 1 和汽车 2，下一辆汽车 2 是基础汽车，汽车 1 是第二辆汽车）

对不起我糟糕的英语

我知道有很多关于生成元素组合的问题，但我认为这个有一定的转折值得提出一个新问题：

对于我的一个宠物项目，我必须预先计算很多状态，以便以后改进应用程序的运行时行为。我努力的步骤之一是：

给定两个整数的 N 个元组（我们从这里开始称它们为点，尽管它们不在我的用例中。但它们大致与 X/Y 相关）我需要计算给定规则的所有有效组合。

规则可能类似于

• “包含的每个点都排除了具有相同 X 坐标的所有其他点”
• “包含的每个点都排除了具有奇数 X 坐标的所有其他点”

我希望并期待这一事实会导致选择过程的改进，但我的数学技能在我打字时才刚刚恢复，我无法想出一个优雅的算法。

• 点集 (N) 开始时很小，但很快就会超过 64 个（对于“使用长作为位掩码”解决方案）
• 我在 C# 中执行此操作，但任何语言的解决方案都应该可以解释基本思想

谢谢。

更新以响应弗拉德的回答：

也许我概括这个问题的想法很糟糕。我上面的规则是即时发明的，只是占位符。一个现实的规则如下所示：

• “包含的每个点都排除了所选点上方三角形中的所有其他点”

根据该规则并选择 (2,1) 我会排除

• (2,2) - 正上方
• (1,3) (2,3) (3,3) - 下一行
• 等等

所以规则是固定的，不是通用的。不幸的是，它们比我最初给出的 X/Y 样本更复杂。

假设我有一个包含单个字符的任意大小的数组。我想计算这些字符的所有可能组合，直到任意长度。

所以假设我的数组是 [1, 2, 3]。用户指定的长度为 2。那么可能的组合为 [11, 22, 33, 12, 13, 23, 21, 31, 32]。

我很难找到一个允许任意长度而不仅仅是排列数组的合适算法。哦，虽然速度不是绝对关键，但它也应该相当快。

假设我有y不同的值，我想x随机选择它们。这样做的有效算法是什么？我可以只打电话给时间，但如果,很大rand() x，性能会很差。xy

请注意，此处需要组合：每个值应该具有相同的选择概率，但它们在结果中的顺序并不重要。当然，任何生成排列的算法都符合条件，但我想知道是否有可能在没有随机顺序要求的情况下更有效地做到这一点。

您如何有效地生成介于 0 和上限 N 之间的 K 个非重复整数的列表，涵盖了这种置换情况。

以前也有人问过类似的问题，但我找不到与我的问题完全匹配的问题。

我有 4 个向量，每个向量包含 200-500 个 4 位整数。每个向量中元素的确切数量各不相同，但我可以将其固定为特定值。我需要找到这 4 个向量中元素的所有可能组合。

例如：

v1[10, 30] v2[11, 45] v3[63, 56] v4[82, 98]

所以我会得到这样的东西：

[10、11、63、82]；[30、11、63、82]；[10、45、63、82]；[10, 45, 56, 82] 等等。

这个算法有一个通用名称，所以我可以在网上找到一些对它的引用吗？否则，在 C++ 中实现这一点的任何技巧都会有所帮助。性能不是什么大问题，因为我只需要运行一次算法。STL 中有内置的东西吗？

我正在寻找并从中map<char, vector<char> >生成每一个可能map<char, char>的结果。

我知道这可能会使用大量内存并需要一些时间。

每个都map<char, char>需要包含每个字母 az，并映射到唯一的 az 字符。IE。ak bj cp dy ev fh ga hb ir jq kn li mx nc oo pz qs rl sd te uw vf wg xm yu zt

到目前为止，这是我为自己得出的结论：

为了将可能组合的荒谬数量减少到较低的数量，如果 avector<char>包含超过 5 个元素，我将简单地将其替换为vector<char>包含来自我的 'master'/'original' 的单个字符的 a map<char, char>。

并非所有字符都会出现vector<char>s在地图的所有区域中。需要找到这些字符并将其放入一些“其他”向量中。

这还应该包含一个字符是多个字符键的唯一可能字符的字符（即我正在使用的示例中的 mw - 我不确定如何处理）。

此“其他”向量应用于不可能具有唯一 az 字符或多个字符具有相同的单个可能字符的情况。

这是我到目前为止的一个例子。

我将采取map<char, vector<char> >，例如：

a: gjkpqvxz
b: gjkpqvxz
c: gjkpqvxyz
d: mw
e: gjkpqvxz
f: nr
g: at
h: cf
i: his
j: gjkpqvxz
k: r
l: h
m: gjkpqvxz
n: gjkpquvxyz
o: is
p: gjkpqvxz
q:是
r: dl
s: l
t: e
u: dgkpuvy
v: cf
w:
bcf x: dguy
y: f
z: at

这是我的起始地图。在切出超过 5 个的大字符向量并用最佳猜测替换它们之后。如果 avector<char>的大小为 1，则该字符映射只有一个组合，并且该字符不能用于任何其他映射，因为它会使其不唯一。我已将其修剪为：

a: k
b: j
c: p
d: mw
e: v
f: n
g: at
h: c
i: is
j: q
k: r
l: h
m: x
n: guy
o: is
p: z
q:是
r: d
s: l
t: e
u: dguy
v: c
w: bc
x: dguy
y: f
z: at

'others' 向量包含 'o' （我认为重要的是要注意，我认为这应该包含上面示例中的 mw 等情况。因为 d 是唯一可以使用 mw 的地方，但显然需要每个字母只能使用一次，只能使用其中一个，而另一个则丢失在某个地方。我不知道如何编写一个一般案例来将这些添加到其他向量中。）

我正在寻找帮助和指示，以生成像这样和这种格式的所有可能map<char, char>。map<char, vector<char> >s它们将用作函数调用中的参数。我不确定从哪里开始写一些一般意义上的东西。我可能会用大量的 for 循环来处理它.

对不起，如果这太像文字墙，或者看起来过于具体或写得不好/问得不好。

我感谢任何和所有的帮助。