阵列路径组合

Question

我不知道如何标题我有问题，所以我不能确定这是以前没有回答。这就是说，以下是我的编程问题的描述。

我有一个R类包含2个整数元素，说X和Y.然后我有两个24元素数组命名为A和B，其中每个元素包含类R的一个实例。我想通过迭代数组来确定如何使用RY填充第三列C如下：

如果RY在索引A的i大于RY在指数越大B的我然后把ř从A到索引i C.

的

如果RY在B的指数i大于在A的指数i的RY时，则将B从B放入C的指数i中。

如果A的指数i处的RY等于指数i处的RY然后把R放入C的索引i中。

这是这些条件中的第三个让我感到困惑。例如，如果数组A和B的索引7,15和19的RY彼此相等，那么我想在C中的那些索引处尝试A和B的每个元素，以基于CRC确定需要哪一个C.的检查，因此我可以把下述R值代入C的相同的索引值：

A [7]，A [15]，A [19]

A [7]，A [15 ]，B [19]

A [7]，B [15]，A [19]

A [7]，B [15]，B [19]

B [7] ，A [15]，A [19]

B [7]，A [15]，B [19]

B [7]，B [15]，A [19]

B [7]，B [15]， B [19]

这8个组合来自2^3（2个数组到RY次数相同的次幂），所以如果我有4个索引在A和B中RY相等，那么那里将是16个组合，5个索引= 32个组合，6 = 64等。

问题是我永远不会知道R和A在所有索引中的次数是否相同;它可能是0到24.因此，为了简短描述一下，我需要一个算法来填充C和A，B中所有可能的R类，其中RY在两个数组中都是相等的，迭代C的所有可能组合并停止当C的第一个实例通过CRC校验时。

听起来很简单吗？但愿如此。让我知道你是否需要更进一步的澄清，或者让我指向一个类似于已经回答的线索。 TIA

Answer 1

我觉得你接近你自己的问题的答案。创建一个数组，列出您必须尝试A或B的所有索引。在示例中，L = {7,15,19}。 n = 3时。然后你将循环从0到2^n-1（含）。在循环的每次迭代中，您将测试每个比特b = 0，比特1，...一直到比特n-1。 L [b]告诉你需要设置哪个索引，并根据该位是否清除，将其设置为相应的A或B值。

最糟糕的情况，虽然你将不得不执行每个24位测试2^24组合。你确定你必须全部尝试吗？

伪代码：

start with empty L; 
for(i=0 to 23) put A[i] or B[i] in C[i] (whichever has larger Y) *or* add i to L (if A.y and B.y match) 
let n=length of L; 
for (x=0 to (1<<n)-1) 
    for(b=0 to n-1) 
     test x&(1<<b), if clear put A[L[b]] in C[L[b]], or put B[L[b]] in C[L[b]] 
    endloop 
    test this array C 
endloop