集合的每个子集的最小和最大元素的或之和

Question

给定一个集合S，对于它的每个非空子集，找到最小和最大的元素并对其进行逻辑或。在所有此类子集中查找这些 OR 的总和。

例如：S = {1, 2, 3}，然后是子集

{1} 最小=1 最大=1 OR=1

{2} 最小=2 最大=2 OR=2

{3} 最小=3 最大=3 OR=3

{1, 2} 最小=1 最大=2 OR=3

{2, 3} 最小=2 最大=3 OR=3

{1, 3} 最小=1 最大=3 OR=3

{1, 2, 3} 最小=1 最大=3 OR=3

答案是 18。

我已阅读但无法在此处使用该逻辑。

Answer 1

算法

对输入数据进行排序
从 i = 0 to n 开始循环，其中 n 是输入的长度，j = i to n，由于输入已排序 input[i] 将是最小的，而 input[j] 将是[i,j]
既然我们知道 input[i] 是最小的，input[j] 是最大的，我们也知道数组的中间元素有 j - i -1，它们的组合将产生相同的结果最低值和最大值因此我们将低值和高值的 OR 乘以这些中间数字可能的排列总数。
例如。对于 input = [1, 2, 3, 4] 和 i = 0 和 j = 3 即）lowest = 1 和 largest = 4 我们知道元素 [2, 3] 可以出现在子集中而不改变最低和最大的价值。 [1, 2, 4], [1, 3, 4], [1, 2, 3, 4] 都有效。中间元素可能的组合数是 2 ^ (count of middle elements).
对所有最低和最大的货币对重复此操作。

这是 C++ 中的代码。

#include <iostream>

int main() {
    vector<int> input {3, 2, 1};
    sort(input.begin(), input.end());
    int answer = 0;
    for(int i=0; i < input.size(); ++i)
    {
        for(int j=i; j < input.size(); ++j)
        {
            int elements = (j - i) - 1;
            int multiple = elements > 0 ? pow(2, elements) : 1;
            answer += ((input[i] | input[j]) * multiple);
            cout << input[i] << ' ' << input[j] << ' ' << answer << endl;
        }
        cout << endl;
    }
    cout <<  answer <<endl;
}

集合的每个子集的最小和最大元素的或之和

Sum of OR of smallest and largest elements of each subset of a set

algorithm

set

subset

logical-operators