1

我有三个整数变量，它们只能取值0和。我想区分我拥有的所有三个数字的组合，排序不算数。假设变量被称为,和。然后和和在这种情况下都是相同的数字，我将这个组合称为。12xyzx=1, y=0, z=0x=0, y=1, z=0x=0, y=0, z=1001

现在有一百种方法可以做到这一点，但我要求一个优雅的解决方案，仅用于教育目的。

我考虑过按001值的数量进行位移：

001 << 0 = 1
001 << 1 = 2
001 << 2 = 4

但随后的数字002和111都会给出6。

4

5 回答 5

7

移位的想法很好，但是您需要2位才能数到 3。因此请尝试移位两倍的位数：

1 << (2*0) = 1
1 << (2*1) = 4
1 << (2*2) = 16

为所有 3 个数字添加这些，前 2 位将计算0您有多少，第二个 2 位将计算多少1，第三个 2 位将计算多少2。

编辑虽然结果是 6 位长（每个数字选项 0、1、2 2 位），但您只需要最低 4 位作为唯一标识符 - 就好像您知道有多少0并且1您有，那么数量也2被确定.

所以而不是做

res = 1<<(2*x);
res+= 1<<(2*y);
res+= 1<<(2*z);

你可以做

res = x*x;
res+= y*y;
res+= z*z;

因为那时

0*0 = 0 // doesn't change result. We don't count 0
1*1 = 1 // we count the number of 1 in the 2 lower bits
2*2 = 4 // we count the number of 2 in the 2 higher bits

因此仅使用 4 位而不是 6 位。

于 2013-11-01T18:53:43.733 回答
4

当不同可能性的数量很少时，可以使用查找表。

首先，对所有可能的三位数组合进行编号，如下所示：

Combinations                  N     Indexes
-------------                 -     ------
000                           0     0
001, 010, 100                 1     1, 3, 9
002, 020, 200                 2     2, 6, 18
011, 101, 110                 3     4, 10, 12
012, 021, 102, 120, 201, 210  4     5, 7, 11, 15, 19, 21
022, 202, 220                 5     8, 20, 24
111                           6     13
112, 121, 211                 7     14, 16, 22
122, 212, 221                 8     17, 23, 25
222                           9     26

第一列显示相同的组合；第二列显示组合的编号（我任意分配它们）；第三列显示每个组合的索引，计算为9*<first digit> + 3*<second digit> + <third digit>。

接下来，为这十个组合中的每一个构建一个查找表，使用这个表达式作为索引：

9*a + 3*b + c

其中a、b和c是您拥有的三个数字。该表如下所示：

int lookup[] = {
    0, 1, 2, 1, 3, 4, 2, 4, 5, 1
,   3, 4, 3, 6, 7, 4, 7, 8, 2, 4
,   5, 4, 7, 8, 5, 8, 9
};

这是对第一个表的重写，索引处的值对应于列中的值N。例如，1在索引1、3和处找到组合数9；组合2位于索引2、6和18，依此类推。

要获得组合的数量，只需检查

int combNumber = lookup[9*a + 3*b + c];
于 2013-11-01T19:08:37.893 回答
1

对于这么小的数字，最简单的方法是单独检查它们，而不是试图花哨，例如：

bool hasZero = false;
bool hasOne = false;
bool hasTwo = false;

// given: char* number or char[] number...

for(int i = 0; i < 3; ++i)
{
    switch (number[i])
    {
        case '0': hasZero = true; break;
        case '1': hasOne = true; break;
        case '2': hasTwo = true; break;
        default: /* error! */ break;
    }
}
于 2013-11-01T18:52:21.437 回答
1

如果我理解正确，您有一些数字序列，可以是 1、2 或 3，它们的排列无关紧要（只是不同的组合）。

既然如此：

std::vector<int> v{1, 2, 3};
std::sort(v.begin(), v.end());

这将使所有不同的组合保持正确对齐，并且您可以轻松编写一个循环来测试是否相等。

或者，您可以使用 a std::array<int, N>（其中 N 是可能值的数量 - 在本例中为 3）。

std::array<int, 3> a;

您将设置a[0]的位置等于1您拥有的 s 的数量，a[1]等于 '2' 的数量等。

// if your string is 111
a[0] = 3;

// if your string is 110 or 011
a[0] = 2;

// if your string is 100 or 010 or 001
a[0] = 1;

// if your string is 120
a[0] = 1;
a[1] = 1;

// if your string is 123
a[0] = 1;
a[1] = 1;
a[2] = 1;

如果您希望将其存储在单个 32 位整数中：

unsigned long x = 1; // number of 1's in your string
unsigned long y = 1; // number of 2's in your string
unsigned long z = 1; // number of 3's in your string
unsigned long result = x | y << 8 | z << 16;

要检索每个的数量，你会做

unsigned long x = result & 0x000000FF;
unsigned long y = (result >> 8) & 0x000000FF;
unsigned long z = (result >> 16) & 0x000000FF;

RBG这与宏中发生的情况非常相似。

于 2013-11-01T18:57:35.400 回答
1 
int n[3]={0,0,0};
++n[x];
++n[y];
++n[z];

现在，在 n 数组中，对于 x、y、z 的每个唯一无序组合，您都有一个唯一的有序值组合。

例如， x=1,y=0,z=0 和 x=0,y=0,z=1 都会给你 n={2,1,0}

于 2013-11-01T19:25:41.710 回答