问题标签 [combinatorics]

我正在尝试解决一个组合数学问题，这似乎很容易，但我遇到了一些麻烦。

如果我最多有 X 张桌子，并且 N 人坐在桌子上，每张桌子可以有 1 到 N 个座位，我只能坐在长方形桌子的一侧（所以人们坐的顺序很重要）。

我想编写一个代码，可以计算从 1 到 K 桌的所有座位分布。

例如，如果我有 12 个人和 1 张桌子，我有 479001600 种座位方式（这很容易计算，我使用了 12 的阶乘）。

但如果我有 12 个人和 3 张桌子，我有 4390848000 种座位方式。我尝试了不同的解决方案，但找不到正确的解决方案。

我尝试将 12 分为 3，然后使用结果的阶乘（它不起作用），我尝试使用 12！* 3（它也没有用）。

有人可以给我一个我可以使用的算法的提示吗？

由于公司的变化，我们不得不重新安排我们的坐姿：一间有10张桌子的房间。由于多种原因，有些办公桌比其他办公桌更受欢迎。一种解决方案是从帽子上画一个桌号。我们认为有更好的方法来做到这一点。

我们有 10 张桌子和 10 个人。让我们给这场比赛的每个人 50 个假想的代币，让他们在桌子上竞标。你在一张桌子上的出价没有限制，你可以把所有 50 个都放，这就是说“我只想坐在这里，期间”。你也可以通过给每张桌子 5 个代币说“我不在乎”。

重要提示：没有人知道其他人在做什么。每个人都必须仅根据他/她的最大利益做出决定（听起来很熟悉？）

现在假设我们得到了这些假设的结果：

现在，我们需要找到一种（或多种）配置，让我们获得最大的满足感（即人们得到他们想要的办公桌，同时考虑到所有的出价并最大化团队的总数。当然，假设是他/她越想要桌子上的人越多）。

由于只有 10 个人，我认为我们可以强制它查看所有可能的配置，但我想知道是否有更好的算法来解决此类问题？

我想用 C++ 中的字符串重复生成所有变体，我非常喜欢非递归算法。我过去提出了一种递归算法，但由于复杂性（r^n），我希望看到一种迭代方法。

我很惊讶我无法在网络或 StackOverflow 上的任何地方找到解决此问题的方法。

我想出了一个 Python 脚本，它也可以执行我想要的操作：

输出：

啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊。

理想情况下，我想要一个 C++ 程序，它可以产生精确的输出，采用完全相同的参数。

这是为了学习目的，不是家庭作业。我希望我的家庭作业是这样的。

这是任务

首先，三个数字的总和是即使只有

我知道

谁能帮我解决这个问题

我决定做一张图片来更好地解释这一点，我只是想检查一下我的想法是否正常，并且我可以将总排列减少 75%：

替代文字 http://www.freeimagehosting.net/uploads/45e5c6b05e.gif

我有 n 个元素需要分成 x 个集合，每个集合必须恰好包含 k=4 个元素。

我需要找到所有可能的分区，其约束条件是每对元素只共享一次相同的集合。

因此，如果我从 [1 2 3 4] [5 6 7 8] [...] 开始，则所有连续的分区都不能容纳例如 [1 2 XX] 或 [XX 1 3]。集合是无序的。

接近这个问题的是第二类斯特林数。但是，它们只解决了任意大小的集合的问题。

示例：我有 32 只老鼠，可以放在 8 个笼子里，每个笼子 4 只。老鼠应该在笼子之间旋转，这样它们就不会遇到另一只老鼠两次。您多久可以这样做一次，配置是什么？

给定两个排序的向量a和b，找出所有向量，它们是 的a和和 的一些排列b，并且一旦排序是唯一的。

您可以通过以下方式创建寻找的向量之一：

• 取向量a和向量的排列b。
  
• 把它们加在一起c[i]=a[i]+b[i]。
  
• 排序c。

我有兴趣找到b产生整个唯一c向量集的 -permutations 集。

示例 0 : a='ccdd'andb='xxyy'
给出求和向量：'cycydxdx', 'cxcxdydy', 'cxcydxdy'.
请注意b:'xyxy'和的排列'yxyx'是相等的，因为在这两种情况下，“box c”和“box d”都恰好得到 one'x'和 one 'y'。

我想这类似于M将球放入M盒子中（每个盒子一个），其中一些球和盒子组是相同的。
更新：给定一个字符串a='aabbbcdddd'，b='xxyyzzttqq'您的问题将是 4 个盒子中的 10 个球。有 4 个大小为 2、3、1 和 4 的不同盒子。球是成对的，无法区分。

示例 1：给定字符串是a='xyy'和b='kkd'。
可能的解决方案：'kkd', 'dkk'.
原因：我们看到所有唯一的排列b是'kkd'和。然而，由于我们的限制，前两个排列被认为是相等的，因为差异映射到string中的相同 char 的索引。'kdk''dkk''y'a

示例 2：给定字符串是a='xyy'and b='khd'。
可能的解决方案：'khd', 'dkh', 'hkd'.

示例 3：给定字符串是a='xxxx'和b='khhd'。
可能的解决方案：'khhd'.

我可以使用Wikipedia/Permutationb中描述的 Narayana Pandita 算法解决生成唯一候选排列的问题。 第二部分接缝更难。我最好的办法是将两个字符串成对加入一个列表，对其进行排序并将其用作查找集中的键。（+连接→<code>'xh','xd' 排序→<code>'xd','xh'）。
'xx''hd'

由于 myM通常非常大，并且字符串中的相似性很常见，因此我目前生成的b排列方式比实际通过 set 过滤器要多得多。我希望有一个算法直接生成正确的算法。欢迎任何改进。

给定 2 个数组Array1 = {a,b,c...n}，Array2 = {10,20,15....x}我如何生成所有可能的组合作为字符串a(i) b(j) c(k) n(p) 其中

如：

所以在所有组合的总数=元素的乘积array2 = (10 X 20 X 15 X ..X x)

类似于笛卡尔积，其中第二个数组定义了第一个数组中每个元素的上限。

具有固定数字的示例，

所以我们将有 3*2*4 = 24 种组合。结果应该是：

我知道 itertools，但它似乎只能生成没有重复的排列。

例如，我想为 2 个骰子生成所有可能的骰子掷骰。所以我需要 [1, 2, 3, 4, 5, 6] 的所有大小为 2 的排列，包括重复：(1, 1), (1, 2), (2, 1)... 等

如果可能的话，我不想从头开始实施

给定一个画布，比方说 10x10，并给定 3 个矩形/正方形。

画布 = 10x10

矩形 1 = 2x2 矩形 2 = 3x3 矩形 3 = 2x4

我创建了一个递归函数，它循环画布上每个矩形的每个位置，它工作正常。（我已经包含了下面的功能，以防有人想看到它，但我认为没有必要）。

我们可以看到矩形 1 和 2 是不可旋转的，即，如果将它们中的任何一个旋转 90 度，它们基本上是相同的形状。但是矩形 3 是可旋转的。

如何更改/构造循环/递归函数，使其循环每个矩形的每个位置以及每个可能的旋转？

目的是遍历画布上所有可能的形状拟合。

谢谢你的帮助！