对于启发式算法,我需要一个接一个地评估特定集合的组合,直到达到停止标准。
由于它们很多,目前我正在使用以下内存高效迭代器块生成它们(受到 python 的启发)itertools.combinations http://docs.python.org/2/library/itertools.html#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();
}
}
问题是,为了大大提高启发式的效率,我需要生成按索引之和排序的这些组合(换句话说,我需要首先生成包含该集合的第一个元素的组合)。
e.g.
考虑集合S = {0,1,2,3,4,5}
(为了简单起见,我选择这个集合,因为元素及其索引一致)。
所有可能的组合r=4
由给定算法生成的数字是:
(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
如您所见,其中的组合并未严格按升序总和排序。
期望的结果如下:
(具有相同总和的组合的顺序并不重要)
(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
grows.
我还快速浏览了组合格雷码,但找不到适合这个问题的人。
您知道如何实施这样的事情吗?
EDIT :
这个问题有一个替代的(不幸的是并不容易)表述。
给定一组S
和一个数字r
,所有可能的总和都很容易找到,因为它们只是第一个总和中的所有数字r
要点S
到最后的总和r
要点S
.
话虽这么说,如果对于每笔金额T
我们可以有效地找到所有具有总和的组合T
我们解决了原来的问题,因为我们只是按升序生成它们。
有效意味着我不想生成所有组合并丢弃具有不同总和的组合。
EDIT 2:
根据@EricLippert的建议,我创建了以下代码:
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),但我仍然担心递归方法的复杂性。事实上,我们似乎正在为每个总和重新生成所有组合,并丢弃那些总和未达到所需值的组合。
为了降低内部函数的复杂性,我找到了一种通过使用有效上限和下限来限制迭代的方法(现在很难说它的复杂性是多少)。
Check 我的答案 https://stackoverflow.com/a/16758273/316644查看最终代码。