组合题
我有一个我认为是“枚举组合”的问题。
我需要从 15 个元素中重复选择 7 个元素，我想知道是否有一种简单的方法可以将所有组合存储在数组中并直接找到我感兴趣的元素。
基本上我正在构建一个大的查找表（包含一个非常昂贵的计算值），我想知道我是否可以使用一个简单的公式访问它（请注意，这不是家庭作业，请检查我的个人资料）。
15 个中有 7 个重复的组合数是 116 280（我仔细检查了它是否正确）。
代码如下：
public static void main(String[] args) {
final Random r = new Random( System.currentTimeMillis() );
final List<String> ls = new ArrayList<String>();
for (int i = 0; i < 15; i++) {
for (int j = i; j < 15; j++) {
for (int k = j; k < 15; k++) {
for (int l = k; l < 15; l++) {
for (int m = l; m < 15; m++) {
for (int n = m; n < 15; n++) {
for (int o = n; o < 15; o++) {
ls.add( i + " " + j + " " + k + " " + l + " " + m + " " + n + " " + o + ": " + r.nextLong() );
}
}
}
}
}
}
}
System.out.println( "We have " + ls.size() + " entries" );
System.out.println( "Entry @ 5,7,2,10,11,8,3 is " + getEntryAt(5,7,2,10,11,8,3) );
}
private static String getEntryAt( int i, int j, int k, int l, int m, int n, int o ) {
return "FILL ME"; // What goes here ?
}
在上面的示例中，我只是在查找数组中放入一个随机值，但这基本上就是这样：我想得到（5,7,2,10,11,8,3），可以我很容易“计算”出它的位置？
请注意，我在数组中存储元素的方式并不重要：我可以以最快的“公式”（如果有的话）的方式存储它们。
如果有人知道我在说什么，我们将非常欢迎任何帮助。
I've got what I think is a "enumerative combinatoric" question.
I need to choose 7 elements out of 15 with repetition and I'd like to know if there's an easy way to store all combination in an array and directly find the element I'm interested in.
Basically I'm building a big lookup table (containing a very expensive to compute value) and I'd like to know if I can access it using a simple formula (note that this is not homework, check my profile).
The number of combinations with repetition for 7 out of 15 is 116 280 (I double checked that it is correct).
Here's the code :
public static void main(String[] args) {
final Random r = new Random( System.currentTimeMillis() );
final List<String> ls = new ArrayList<String>();
for (int i = 0; i < 15; i++) {
for (int j = i; j < 15; j++) {
for (int k = j; k < 15; k++) {
for (int l = k; l < 15; l++) {
for (int m = l; m < 15; m++) {
for (int n = m; n < 15; n++) {
for (int o = n; o < 15; o++) {
ls.add( i + " " + j + " " + k + " " + l + " " + m + " " + n + " " + o + ": " + r.nextLong() );
}
}
}
}
}
}
}
System.out.println( "We have " + ls.size() + " entries" );
System.out.println( "Entry @ 5,7,2,10,11,8,3 is " + getEntryAt(5,7,2,10,11,8,3) );
}
private static String getEntryAt( int i, int j, int k, int l, int m, int n, int o ) {
return "FILL ME"; // What goes here ?
}
In the above example I'm just putting a random value in the lookup array but this is basically it: I want to get, say, (5,7,2,10,11,8,3), can I "compute" easily it's location?
Note that the way I'm storing elements in the array has no importance: I can store them in the way that makes for the fastest "formula", if any.
If anyone knows what I'm talking about any help would be much welcome.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
分解它的简单方法是将计数作为部分求和。 （对于我的示例，我使用基于 1 的索引）
假设您给出了（位数较少，但原理相同）元组 ( 2, 3, 4 )。它的位置只是以下各项的总和：
你可以通过迭代的方式来解决这个问题。
现在，对于 D = 3 位数字和 K 个项目，您可以绘制模式并查看它如何增长：
对于每次迭代，您所做的实际上是采用先前的分组（包括空分组）并添加一个附加数字——就像三角形数列一样。您甚至可以在增加第一位数字时递归地思考这一点 - 在上面的 D = 3，K = 3 的示例中，您可以重新映射不以“1”开头的内容的符号，因此它们不包含任何“1” - D 仍然是 3，但 K 现在是 2：
变成：
这就是您添加到 K 的方式。（对于 D = 3，请注意它们是三角形数。）
添加一个怎么样？数字？好吧，对于 K = 3，D = 3，您可以想象一下：
并在它们前面添加一个数字。您可以在所有这些前面添加“1”。只能在“2”或更高的前面添加“2”，在只有“3”的前面添加“3”。现在您可以看到递归结构。
举一个简单的例子，要找到 ( 2, 4, 4 ) 的索引，其中 D = 3, K = 5：
所以索引( 2, 4, 4 ) = 22
现在棘手的部分是计算 count( D, K ) ，实际上就是 C( K + D - 1, D )。您现在可以将其推广到 K = 15，D = 7。
The simple way to break it down is to sum the counts as parts. (For my examples, I used 1-based index)
Let's say you're given (fewer digits, but same principle) the tuple ( 2, 3, 4 ). Its position is simply the sum of:
and you can figure this out iteratively.
Now, for D = 3 digits, and K items, you can draw out the pattern and see how it grows:
for each iteration, what you're doing is actually taking the previous groupings (include an empty grouping) and adding an additional number -- as in the triangular number sequence. You can even think of this recursively as you increase the first digit -- in the above example of D = 3, K = 3, you can re-map the symbols of the stuff that doesn't start with "1", and thus they do not contain any "1"s - D is still 3, but K is now 2:
becomes:
This is how you would add to K. (For D = 3, notice that they are triangular numbers.)
How about adding a digit? Well, for K = 3, D = 3, you can imagine, given this:
and add a digit in front of them. You can add "1" in front of all of them. You can only add "2" in front of the "2" or higher, and "3" to the one with only "3"s. Now you can see the recursive structure.
For a simple example, to find the index of ( 2, 4, 4 ) with D = 3, K = 5:
So index( 2, 4, 4 ) = 22
Now the tricky part is figuring out count( D, K ), which is actually just C( K + D - 1, D ). You can now generalize this to your K = 15, D = 7.
在深度嵌套的 for 循环中：
对于 get 语句，它就像这样简单：
但为此， ls 需要作为参数传递给 getter 函数，或者需要是全局的。
and in your deeply nested for loops:
and for your get statements, it's as simple as:
But for this, ls needs to be either passed as a parameter to the getter function or it needs to be global.
构建一棵高度为 7 的树。根节点有 15 个子节点，命名为 1-15。每个孩子的名字都对应于集合中该数字的选择。编号为 n 的节点具有编号为 m 的子节点（n <= m <= 15）
在树的叶子（全部 116 280 个叶子，深度均为 7）处，您链接到该组合的预先计算的解决方案。
然后，查找给定集合的解决方案需要您跟踪树中的相关路径，这可以在恒定时间内完成。
Build a tree of height 7. The root node has 15 children, named 1-15. Each child name corresponds to the selection of that number in the set. A node with number n has children with numbers m (n <= m <= 15)
At the leaves of the tree (all 116 280 of them, all have depth 7) you link to the pre-computed solution for that combination.
Looking up the solution for a given set then requires you tracing the relevant path through the tree, which can be done in constant time.
也许您可以使用组合数字系统来解决您的问题？
Perhaps you could use combinatorial number system to solve your problem?
似乎您想要一个
Map，其中T是计算成本高昂的值的类型。HashMap将在内部使用数组，所以我猜这是一个有效的答案。将键设置为
Multiset的要点在于，如果两个多重集包含的每个元素的编号相同，则多重集上的equals()方法应将它们视为相等，而不考虑它们订购。 （顺便说一下，JDK 没有 Multiset 类，但您可以找到第三方 Multiset 类。）Seems like you want a
Map<Multiset,T>whereTis the type of your expensive-to-compute value(s). AHashMap<Multiset,T>would use an array internally, so I guess that is a valid answer.The point of making the key a
Multisetis that theequals()method on the multiset should consider two multisets to be equal if they contain the same numbers of each element, disregarding ordering. (By the way, the JDK doesn't have aMultisetclass, but you can find third-party Multiset classes.)