2

其实这个问题可以概括如下：

从给定的一组元素中找到满足特定条件的所有可能组合。

那么，有什么好的算法吗？

4

8 回答 8

9

只有 16 种可能性（其中之一是将“没有”加在一起，这不会给你 24），所以老式的“蛮力”算法对我来说看起来不错：

for (unsigned int choice = 1; choice < 16; ++choice) {
    int sum = 0;
    if (choice & 1) sum += elements[0];
    if (choice & 2) sum += elements[1];
    if (choice & 4) sum += elements[2];
    if (choice & 8) sum += elements[3];
    if (sum == 24) {
        // we have a winner
    }
}

在您的问题的完全一般形式中，判断组合是否符合“某些标准”的唯一方法是评估每个组合的这些标准。鉴于有关标准的更多信息，也许您可​​以制定一些方法来避免测试每种组合并相应地构建算法，但不能没有这些细节。再次，蛮力为王。

于 2012-05-16T09:28:46.783 回答
2

在Wikipedia和MathWorld中有两个关于求和问题的有趣解释。

对于您提出的第一个问题，第一个答案适用于有限数量的元素。您应该意识到 Jessop 先生使用 16 作为循环边界的原因是因为这是 2^4，其中 4 是您的集合中的元素数。如果您有 100 个元素，则循环限制将变为 2^100，并且您的算法实际上需要永远完成。

在有界和的情况下，您应该考虑深度优先搜索，因为当元素的总和超过您要查找的总和时，您可以修剪分支并回溯。

在一般问题的情况下，找到满足特定标准的元素子集，这被称为背包问题，它被称为 NP-Complete。鉴于此，没有任何算法可以在小于指数的时间内解决它。

尽管如此，还是有几种启发式方法可以带来很好的结果，包括（但不限于）遗传算法（我个人很喜欢，因为我写了一本关于它们的书）和动态规划。在 Google 中进行简单搜索将显示许多描述该问题的不同解决方案的科学论文。

于 2012-06-04T14:23:45.963 回答
1

从给定的一组元素中找到满足特定条件的所有可能组合

如果我对您的理解正确，此代码将对您有所帮助：

    >>> from itertools import combinations as combi    
    >>> combi.__doc__
'combinations(iterable, r) --> combinations object\n\nReturn successive r-length
 combinations of elements in the iterable.\n\ncombinations(range(4), 3) --> (0,1
,2), (0,1,3), (0,2,3), (1,2,3)'
    >>> set = range(4)
    >>> set
    [0, 1, 2, 3]
    >>> criteria = range(3)
    >>> criteria
    [0, 1, 2]
    >>> for tuple in list(combi(set, len(criteria))):
    ...     if cmp(list(tuple), criteria) == 0:
    ...             print 'criteria exists in tuple: ', tuple
    ...
    criteria exists in tuple:  (0, 1, 2)

    >>> list(combi(set, len(criteria)))
    [(0, 1, 2), (0, 1, 3), (0, 2, 3), (1, 2, 3)]
于 2012-05-16T08:34:21.733 回答
0

(n X n ) 建立一个 nxn 的方阵

并将其对应的交叉值一起打印

例如

1 2 3 4

1 11 12 13 14

2 .. .. .. ..

3..

4 ....

于 2012-06-05T02:46:28.893 回答
0

输入数字集很重要，因为您可以在您的起始集中允许负数、虚数、有理数等。您还可以限制为所有偶数、所有奇数输入等。

这意味着很难建立演绎的东西。您需要蛮力，也就是尝试每种组合等。

在这个特定的问题中，您可以构建一个递归的算法 - 例如，找到加起来为 23 的 3 个 Int ( 1,22 ) 的每个组合，然后加 1，每个组合加到 22 并加 2 等等。这又可以被打破到 2 的每个组合中，加起来为 21 等。您需要决定是否可以两次计算相同的数字。

一旦你有了它，你就有一个递归函数可以调用 -

combinations( 24 , 4 ) = combinations( 23, 3 ) + combinations( 22, 3 ) + ... combinations( 4, 3 );
combinations( 23 , 3 ) = combinations( 22, 2 ) + ... combinations( 3, 2 );

ETC

这很好用，除非您必须小心在递归中重复数字。

于 2012-06-04T21:54:44.840 回答
0

如果我正确理解您的问题，您所要求的称为“排列”或从一组 (Y) 数字中排列 (X) 数字的可能方法的数量 (N)。

N = Y! / (Y - X)!

我不知道这是否会有所帮助，但这是我为排列分配提出的解决方案。

你有一个输入：123（字符串）使用 substr 函数

1）将输入的每个数字放入一个数组中

array[N1,N2,N3,...]

2）创建交换函数

function swap(Number A, Number B)
{
   temp = Number B 
   Number B = Number A   
   Number A = temp   
}

3）该算法使用交换函数来移动数字，直到完成所有排列。

original_string= '123'    
temp_string=''

While( temp_string != original_string)
{
   swap(array element[i], array element[i+1])

   if (i == 1)
       i == 0

   temp_string = array.toString
   i++
}

希望您可以遵循我的伪代码，但这至少适用于 3 位数排列

于 2012-06-05T01:49:23.490 回答
0

通常对于这样的问题，您必须尝试所有的可能性，如果您知道代码不满足标准，您应该做的事情是让代码中止构建组合（如果您的标准是您没有两个以上的蓝色球，那么你必须中止超过两个的计算）。回溯

def perm(set,permutation): 
    if lenght(set) == lenght(permutation):
       print permutation
    else:
        for element in set:
           if permutation.add(element) == criteria:
               perm(sett,permutation)
           else:
                permutation.pop()  //remove the element added in the if
于 2012-05-30T15:33:57.110 回答
0 
    private int[][] work()
    {
        const int target = 24;
        List<int[]> combos = new List<int[]>();

        for(int i = 0; i < 9; i++)
            for(int x = 0; x < 9; x++)
                for(int y = 0; y < 9; y++)
                    for (int z = 0; z < 9; z++)
                    {
                        int res = x + y + z + i;
                        if (res == target)
                        {
                            combos.Add(new int[] { x, y, z, i });
                        }
                    }
        return combos.ToArray();
    }

它立即起作用，但可能有更好的方法而不是“猜测和检查”。我所做的就是遍历所有可能性，将它们加在一起，看看它是否达到目标值。

于 2012-06-04T23:58:03.113 回答