生成按属性排序的组合

Question

我正在寻找一种方法来生成按单个属性排序的对象组合。 我不认为字典顺序是我正在寻找的......我会尝试举一个例子。 假设我有一个对象 A、B、C、D 列表，其中我想要按 3、3、2、1 排序的属性值。 这给出了 A3、B3、C2、D1 对象。 现在我想生成2个对象的组合，但它们需要按降序排列：

• A3 B3
• A3 C2
• B3 C2
• A3 D1
• B3 D1
• C2 D1

生成所有组合并对它们进行排序是不可接受的，因为现实世界场景涉及大集合以及数以百万计的组合。 （一组 40 个，顺序为 8 个），我只需要高于特定阈值的组合。

实际上，我需要对高于阈值的组合进行计数，并按给定属性的总和进行分组，但我认为这要困难得多 - 所以我会满足于开发高于阈值的所有组合并对它们进行计数。 如果可能的话。

编辑 - 我原来的问题不是很精确......我实际上不需要订购这些组合，只是认为这将有助于隔离高于阈值的组合。 更准确地说，在上面的示例中，给定阈值 5，我正在寻找给定集合产生 1 个总和为 6 ( A3 B3 ) 的组合和 2 个总和为 5 ( A3 C2 ) 的信息， B3 C2)。 我实际上不需要组合本身。

我正在研究子集和问题，但如果我正确理解给定的动态解决方案，它只会向您提供是否有给定总和的信息，而不是总和的计数。

谢谢

Answer 1

实际上，我认为您确实想要字典顺序，但是降序而不是升序。 另外：

• 根据您的描述，我不清楚 A、B、...D 在您的答案中发挥任何作用（除了可能作为值的容器）。
• 我认为你的问题示例只是“对于每个至少为 5 的整数，直到两个值的最大可能总数，集合 {3, 3, 2, 1} 中有多少个不同的对具有该整数的总和？”
• 有趣的部分是一旦无法达成可能的解决方案（剩余可实现的金额太小）时的早期救助。

我稍后会发布示例代码。

这是我承诺的示例代码，下面有一些注释：

public class Combos {

    /* permanent state for instance */
    private int values[];
    private int length;

    /* transient state during single "count" computation */
    private int n;
    private int limit;
    private Tally<Integer> tally;
    private int best[][];  // used for early-bail-out

    private void initializeForCount(int n, int limit) {
        this.n = n;
        this.limit = limit;
        best = new int[n+1][length+1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= length - i; ++j) {
                best[i][j] = values[j] + best[i-1][j+1];
            }
        }
    }

    private void countAt(int left, int start, int sum) {
        if (left == 0) {
            tally.inc(sum);
        } else {
            for (
                int i = start;
                i <= length - left
                && limit <= sum + best[left][i];  // bail-out-check
                ++i
            ) {
                countAt(left - 1, i + 1, sum + values[i]);
            }
        }
    }

    public Tally<Integer> count(int n, int limit) {
        tally = new Tally<Integer>();
        if (n <= length) {
            initializeForCount(n, limit);
            countAt(n, 0, 0);
        }
        return tally;
    }

    public Combos(int[] values) {
        this.values = values;
        this.length = values.length;
    }

}

前言注释：

这使用了一个名为 Tally 的小辅助类，它只是隔离制表（包括从不初始化） -之前见过的钥匙）。 我会把它放在最后。

为了保持简洁，我采取了一些对于“真实”代码来说不是很好的做法的快捷方式：

• 这不会检查空值数组等。
• 我假设值数组已经按降序排序，这是必需的用于早期救助技术。 （好的生产代码将包括排序。）
• 我将瞬态数据放入实例变量中，而不是将它们作为支持 count 的私有方法之间的参数传递。 这使得该类成为非线程安全的。

说明：

使用要组合的（降序排列）整数数组创建 Combos 实例。 value 数组每个实例设置一次，但可以根据不同的群体大小和限制对 count 进行多次调用。

count 方法触发对 values 中 n 个整数的唯一组合的（大部分）标准递归遍历。 limit 参数给出了利息总和的下限。

countAt 方法检查 values 中的整数组合。 left 参数是剩余多少个整数来组成总和中的 n 个整数，start 是 values 中的位置> 从中搜索，sum 是部分和。

早期纾困机制基于计算best，这是一个二维数组，指定从给定状态可达到的“最佳”总和。 best[n][p] 中的值是从原始值<的位置 p 开始的 n 个值的最大和。 /代码>。

当正确的总体累积完毕后，countAt 的递归就会触底； 这会将当前的总和（n 值）添加到tally 中。 如果 countAt 尚未触底，它会从 start-ing 位置扫描 values 以增加当前的部分 sum >，只要：

• values 中保留足够的位置来实现指定的总体，并且
• 剩余的最佳（最大）小计足够大以达到限制< /代码>。

使用您的问题数据运行示例：

    int[] values = {3, 3, 2, 1};
    Combos mine = new Combos(values);
    Tally<Integer> tally = mine.count(2, 5);
    for (int i = 5; i < 9; ++i) {
        int n = tally.get(i);
        if (0 < n) {
            System.out.println("found " + tally.get(i) + " sums of " + i);
        }
    }

产生您指定的结果：

found 2 sums of 5
found 1 sums of 6

这是 Tally 代码：

public static class Tally<T> {
    private Map<T,Integer> tally = new HashMap<T,Integer>();
    public Tally() {/* nothing */}
    public void inc(T key) {
        Integer value = tally.get(key);
        if (value == null) {
            value = Integer.valueOf(0);
        }
        tally.put(key, (value + 1));
    }
    public int get(T key) {
        Integer result = tally.get(key);
        return result == null ? 0 : result;
    }
    public Collection<T> keys() {
        return tally.keySet();
    }
}

Answer 2

我编写了一个类来处理处理二项式系数的常用函数，这是您的问题所属的问题类型。 它执行以下任务：

1. 以良好的格式将任意 N 选择 K 的所有 K 索引输出到文件中。 K 索引可以替换为更具描述性的字符串或字母。 这种方法使得解决此类问题变得非常简单。

2. 将 K 索引转换为排序二项式系数表中条目的正确索引。 该技术比依赖迭代的旧发布技术要快得多。 它通过使用帕斯卡三角形固有的数学属性来实现这一点。 我的论文谈到了这一点。 我相信我是第一个发现并发布此技术的人，但我可能是错的。

3. 将排序二项式系数表中的索引转换为相应的 K 索引。

4. 使用Mark Dominus方法来计算二项式系数，这种方法不太可能溢出并适用于更大的数字。

5. 该类是用 .NET C# 编写的，并提供了一种使用通用列表来管理与问题相关的对象（如果有）的方法。 该类的构造函数采用一个名为 InitTable 的布尔值，当该值为 true 时，将创建一个通用列表来保存要管理的对象。 如果该值为 false，则不会创建该表。 执行上述 4 种方法不需要创建该表。 提供了访问器方法来访问表。

6. 有一个关联的测试类，它显示了如何使用该类及其方法。 它已经过 2 个案例的广泛测试，没有已知的错误。

要了解此类并下载代码，请参阅制表二项式系数。

Answer 3

在 stackoverflow 中查看这个问题：返回所有组合的算法

我也只是使用下面的java代码来生成所有排列，但它可以很容易地用于生成给定索引的唯一组合。

public static <E> E[] permutation(E[] s, int num) {//s is the input elements array and num is the number which represents the permutation

    int factorial = 1;

    for(int i = 2; i < s.length; i++)
        factorial *= i;//calculates the factorial of (s.length - 1)

    if (num/s.length >= factorial)// Optional. if the number is not in the range of [0, s.length! - 1] 
        return null;

    for(int i = 0; i < s.length - 1; i++){//go over the array

        int tempi = (num / factorial) % (s.length - i);//calculates the next cell from the cells left (the cells in the range [i, s.length - 1])
        E temp = s[i + tempi];//Temporarily saves the value of the cell needed to add to the permutation this time 

        for(int j = i + tempi; j > i; j--)//shift all elements to "cover" the "missing" cell
            s[j] = s[j-1];

        s[i] = temp;//put the chosen cell in the correct spot

        factorial /= (s.length - (i + 1));//updates the factorial

    }

    return s;
}

Answer 4

我非常抱歉（在评论中进行了所有这些澄清之后）我无法找到解决此问题的有效方法。 我尝试了过去一个小时但没有结果。

原因（我认为）是这个问题与旅行商问题非常相似。 除非您尝试所有组合，否则无法知道哪些属性将达到阈值。

似乎没有什么巧妙的技巧可以解决这类问题。

您仍然可以对实际代码进行许多优化。

尝试根据属性对数据进行排序。 当您发现较高的值无法满足阈值时，您可以避免处理列表中的某些值（因此可以消除所有较低的值）。

Answer 5

如果您使用 C#，此处有一个相当不错的泛型库。 但请注意，某些排列的生成不按字典顺序排列

Answer 6

下面是计算这些子集数量的递归方法：我们定义一个函数 count(minIndex,numElements,minSum)，它返回大小为 numElements 的子集数量 其总和至少为 minSum，包含索引为 minIndex 或更大的元素。

正如问题陈述中一样，我们按降序对元素进行排序，例如 [3,3,2,1]，并将第一个索引称为零，元素总数为 N。我们假设所有元素都是非负的。 要查找总和至少为 5 的所有 2 子集，我们调用 count(0,2,5)。

示例代码 (Java)：

int count(int minIndex, int numElements, int minSum)
{
    int total = 0;

    if (numElements == 1)
    {
        // just count number of elements >= minSum
        for (int i = minIndex; i <= N-1; i++)
            if (a[i] >= minSum) total++; else break;
    }
    else
    {
        if (minSum <= 0)
        {
            // any subset will do (n-choose-k of them)
            if (numElements <= (N-minIndex))
                total = nchoosek(N-minIndex, numElements);
        }
        else
        {
            // add element a[i] to the set, and then consider the count
            // for all elements to its right
            for (int i = minIndex; i <= (N-numElements); i++)
                total += count(i+1, numElements-1, minSum-a[i]);
        }
    }

    return total;
}

顺便说一句，我已经使用包含 40 个元素和大小为 8 的子集的数组运行了上面的代码，并且始终在不到一秒的时间内返回结果。