有效的方式来产生通过组合指数之和有序增加 [英] Efficient way to generate combinations ordered by increasing sum of indexes
问题描述
对于启发式算法，我需要其他的后评估，一，一组特定的组合，直到我达到停止标准。
For a heuristic algorithm I need to evaluate, one after the other, the combinations of a certain set until I reach a stop criterion.
由于他们很多，此刻我用下面的内存使用效率，迭代器块生成它们（灵感来自Python的的 itertools.combinations ）：
Since they are a lot, at the moment I'm generating them using the following memory efficient iterator block (inspired by python's itertools.combinations):
public static IEnumerable<T[]> GetCombinations<T>(this IList<T> pool, int r)
{
int n = pool.Count;
if (r > n)
throw new ArgumentException("r cannot be greater than pool size");
int[] indices = Enumerable.Range(0, r).ToArray();
yield return indices.Select(idx => pool[idx]).ToArray();
while (true)
{
int i;
for (i = r - 1; i >= 0; i--)
if (indices[i] != i + n - r)
break;
if (i < 0)
break;
indices[i] += 1;
for (int j = i + 1; j < r; j++)
indices[j] = indices[j - 1] + 1;
yield return indices.Select(idx => pool[idx]).ToArray();
}
}
问题是，大大提高工作效率我启发式，我需要生成这些组合由这些指标的总和排序（在我必须先产生换言之，含有该组的第一个元件的组合）。
The problem is, to greatly improve the efficiency of my heuristic, I'd need to generate these combinations sorted by the sum of they indexes (in other words I need to generate first, the combinations containing the first elements of the set).
如：结果
考虑集 S = {0,1,2,3， 4,5} 结果
（我选择这套为简单，因为元素和它们的指标相一致）。结果
的所有可能的组合R = 4 从给定的算法生成的数字是：
e.g.
Consider the set S = {0,1,2,3,4,5}
(I choose this set for simplicity since elements and their indexes coincide).
All possible combinations of r=4 numbers generated from the given algorithm are:
(0, 1, 2, 3) SUM: 6
(0, 1, 2, 4) SUM: 7
(0, 1, 2, 5) SUM: 8
(0, 1, 3, 4) SUM: 8
(0, 1, 3, 5) SUM: 9
(0, 1, 4, 5) SUM: 10
(0, 2, 3, 4) SUM: 9
(0, 2, 3, 5) SUM: 10
(0, 2, 4, 5) SUM: 11
(0, 3, 4, 5) SUM: 12
(1, 2, 3, 4) SUM: 10
(1, 2, 3, 5) SUM: 11
(1, 2, 4, 5) SUM: 12
(1, 3, 4, 5) SUM: 13
(2, 3, 4, 5) SUM: 14
在这里，你可以看到，该组合没有严格按升序排序的总和。
where, as you can see, the combinations are not strictly sorted by ascending sum.
期望的结果是不是以下：结果，
（具有相同的总和的组合的顺序并不重要）
The desired outcome is instead the following :
(the order of the combinations having the same sum is not important)
(0, 1, 2, 3) SUM: 6
(0, 1, 2, 4) SUM: 7
(0, 1, 2, 5) SUM: 8
(0, 1, 3, 4) SUM: 8
(0, 1, 3, 5) SUM: 9
(0, 2, 3, 4) SUM: 9
(0, 1, 4, 5) SUM: 10
(0, 2, 3, 5) SUM: 10
(1, 2, 3, 4) SUM: 10
(0, 2, 4, 5) SUM: 11
(1, 2, 3, 5) SUM: 11
(0, 3, 4, 5) SUM: 12
(1, 2, 4, 5) SUM: 12
(1, 3, 4, 5) SUM: 13
(2, 3, 4, 5) SUM: 14
一个平凡的解决方案是根据它们的和产生所有的组合，然后对它们进行排序;但这不是真正有效/可行的，因为作为 N 的增长。
A trivial solution would be to generate all the combinations then sort them according to their sum; but this is not really efficient/feasible since the number of combinations becomes huge as n grows.
我也有组合的数量变得庞大咋一看，以组合格雷码，但我无法找到适合这个问题的人。
I also had a quick look to combinatorial Gray Codes but I couldn't find anyone suitable for this problem.
你有没有关于如何实现这样的想法？
Do you have an idea on how to implement something like this ?
编辑：
这问题有一个备用（可惜不是更容易）制定
给定一组取值等一批研究，所有可能的资金是微不足道的发现，因为他们仅仅是全部来自取值首研究元素到最后的总和<$总和的数字C $ç>研究 的S元素。
This problem has an alternate (unfortunately not easier) formulation.
Given a set S and a number r, all the possible sums are trivial to find, since they are simply all the numbers from the sum of the first r elements of S to the sum of the last r elements of S.
话虽这么说，如果每个总和 T 我们可以efficiently¹发现有一笔 T 我们解决了原来的问题，因为我们只是生成它们的所有组合按升序排列。
That being said, if, for each sum T we can efficiently¹ find all the combinations having sum T we solve the original problem since we simply generate them in ascending order.
¹有效地意味着我不想产生所有的组合并丢弃具有不同金额的人。
¹ efficiently means that I don't want to generate all the combinations and discard the ones having a different sum.
编辑2：
在@EricLippert建议我创建了以下代码：
After @EricLippert suggestion I created the following code:
public static IEnumerable<T[]>
GetCombinationsSortedByIndexSum<T>(this IList<T> pool, int r)
{
int n = pool.Count;
if (r > n)
throw new ArgumentException("r cannot be greater than pool size");
int minSum = ((r - 1) * r) / 2;
int maxSum = (n * (n + 1)) / 2 - ((n - r - 1) * (n - r)) / 2;
for (int sum = minSum; sum <= maxSum; sum++)
{
foreach (var indexes in AllMonotIncrSubseqOfLenMWhichSumToN(0, n - 1, r, sum))
yield return indexes.Select(x => pool[x]).ToArray();
}
}
static IEnumerable<IEnumerable<int>>
AllMonotIncrSubseqOfLenMWhichSumToN(int seqFirstElement, int seqLastElement, int m, int n)
{
for (int i = seqFirstElement; i <= seqLastElement - m + 1; i++)
{
if (m == 1)
{
if (i == n)
yield return new int[] { i };
}
else
{
foreach (var el in AllMonotIncrSubseqOfLenMWhichSumToN(i + 1, seqLastElement, m - 1, n - i))
yield return new int[] { i }.Concat(el);
}
}
}
这工作正常（希望是什么意思埃里克：P），但我仍然关心递归方法的复杂性。事实上，它似乎，我们正在为再生每笔丢弃的那些没有总结到期望值的所有组合。
This works fine (hopefully is what Eric meant :P) but I'm still concerned about the complexity of the recursive method. In fact it seems that we're regenerating all the combinations for each sum discarding the ones not summing up to the desired value.
要减少内部函数I的复杂性发现了一种通过有效的上限和下限（现在它真的很难说什么的这种复杂性）来限制迭代。
To reduce the complexity of the inner function I found a way to limit the iterations by using effective upper and lower bounds (and now it's really hard to say what is the complexity of this).
检查的my回答看到最后的代码。
Check my answer to see the final code.
推荐答案
我想到的解决办法是：
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
// Preconditions:
// * items is a sequence of non-negative monotone increasing integers
// * n is the number of items to be in the subsequence
// * sum is the desired sum of that subsequence.
// Result:
// A sequence of subsequences of the original sequence where each
// subsequence has n items and the given sum.
static IEnumerable<IEnumerable<int>> M(IEnumerable<int> items, int sum, int n)
{
// Let's start by taking some easy outs. If the sum is negative
// then there is no solution. If the number of items in the
// subsequence is negative then there is no solution.
if (sum < 0 || n < 0)
yield break;
// If the number of items in the subsequence is zero then
// the only possible solution is if the sum is zero.
if (n == 0)
{
if (sum == 0)
yield return Enumerable.Empty<int>();
yield break;
}
// If the number of items is less than the required number of
// items, there is no solution.
if (items.Count() < n)
yield break;
// We have at least n items in the sequence, and
// and n is greater than zero, so First() is valid:
int first = items.First();
// We need n items from a monotone increasing subsequence
// that have a particular sum. We might already be too
// large to meet that requirement:
if (n * first > sum)
yield break;
// There might be some solutions that involve the first element.
// Find them all.
foreach(var subsequence in M(items.Skip(1), sum - first, n - 1))
yield return new[]{first}.Concat(subsequence);
// And there might be some solutions that do not involve the first element.
// Find them all.
foreach(var subsequence in M(items.Skip(1), sum, n))
yield return subsequence;
}
static void Main()
{
int[] x = {0, 1, 2, 3, 4, 5};
for (int i = 0; i <= 15; ++i)
foreach(var seq in M(x, i, 4))
Console.WriteLine("({0}) SUM {1}", string.Join(",", seq), i);
}
}
输出是你所需的输出。
我没有尝试优化此。这将是有趣的来分析一下，看看那里的大部分时间都花在。
I've made no attempt to optimize this. It would be interesting to profile it and see where most of the time is spent.
更新：只是为了好玩，我写一个使用一成不变的堆栈，而不是任意枚举一个版本。 ！享受
UPDATE: Just for fun I wrote a version that uses an immutable stack instead of an arbitrary enumerable. Enjoy!
using System;
using System.Collections.Generic;
using System.Linq;
abstract class ImmutableList<T> : IEnumerable<T>
{
public static readonly ImmutableList<T> Empty = new EmptyList();
private ImmutableList() {}
public abstract bool IsEmpty { get; }
public abstract T Head { get; }
public abstract ImmutableList<T> Tail { get; }
public ImmutableList<T> Push(T newHead)
{
return new List(newHead, this);
}
private sealed class EmptyList : ImmutableList<T>
{
public override bool IsEmpty { get { return true; } }
public override T Head { get { throw new InvalidOperationException(); } }
public override ImmutableList<T> Tail { get { throw new InvalidOperationException(); } }
}
private sealed class List : ImmutableList<T>
{
private readonly T head;
private readonly ImmutableList<T> tail;
public override bool IsEmpty { get { return false; } }
public override T Head { get { return head; } }
public override ImmutableList<T> Tail { get { return tail; } }
public List(T head, ImmutableList<T> tail)
{
this.head = head;
this.tail = tail;
}
}
System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
public IEnumerator<T> GetEnumerator()
{
for (ImmutableList<T> current = this; !current.IsEmpty; current = current.Tail)
yield return current.Head;
}
}
class Program
{
// Preconditions:
// * items is a sequence of non-negative monotone increasing integers
// * n is the number of items to be in the subsequence
// * sum is the desired sum of that subsequence.
// Result:
// A sequence of subsequences of the original sequence where each
// subsequence has n items and the given sum.
static IEnumerable<ImmutableList<int>> M(ImmutableList<int> items, int sum, int n)
{
// Let's start by taking some easy outs. If the sum is negative
// then there is no solution. If the number of items in the
// subsequence is negative then there is no solution.
if (sum < 0 || n < 0)
yield break;
// If the number of items in the subsequence is zero then
// the only possible solution is if the sum is zero.
if (n == 0)
{
if (sum == 0)
yield return ImmutableList<int>.Empty;
yield break;
}
// If the number of items is less than the required number of
// items, there is no solution.
if (items.Count() < n)
yield break;
// We have at least n items in the sequence, and
// and n is greater than zero.
int first = items.Head;
// We need n items from a monotone increasing subsequence
// that have a particular sum. We might already be too
// large to meet that requirement:
if (n * first > sum)
yield break;
// There might be some solutions that involve the first element.
// Find them all.
foreach(var subsequence in M(items.Tail, sum - first, n - 1))
yield return subsequence.Push(first);
// And there might be some solutions that do not involve the first element.
// Find them all.
foreach(var subsequence in M(items.Tail, sum, n))
yield return subsequence;
}
static void Main()
{
ImmutableList<int> x = ImmutableList<int>.Empty.Push(5).
Push(4).Push(3).Push(2).Push(1).Push(0);
for (int i = 0; i <= 15; ++i)
foreach(var seq in M(x, i, 4))
Console.WriteLine("({0}) SUM {1}", string.Join(",", seq), i);
}
}
这篇关于有效的方式来产生通过组合指数之和有序增加的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
