Комбинации путей массива - PullRequest
Новая
       0

Комбинации путей массива

0 голосов
/ 01 марта 2011

Я не уверен, как озаглавить вопрос, который у меня есть, поэтому я не уверен, что на него раньше не отвечали. Тем не менее, ниже приводится описание моего вопроса программирования.

У меня есть класс R, содержащий 2 целочисленных элемента, скажем, X и Y. Затем у меня есть два массива из 24 элементов с именами A и B, где каждый элемент содержит экземпляр класса R. Я хотел бы перебрать массивы, чтобы определить, как использовать RY для заполнения третьего массива C следующим образом:

Если R.Y по индексу i из A больше, чем R.Y по индексу i из B, тогда положить R из A в индекс i из C.

Если R.Y по индексу i в B больше, чем R.Y по индексу i из A, тогда положить R из B в индекс i из C.

Если R.Y по индексу i из A равно R.Y по индексу i из B, то поместить R в индекс i из C.

Это третье из этих состояний, которое меня озадачило. Например, если индексы 7, 15 и 19 массивов A и B имеют RY, равные друг другу, я хочу попробовать каждый элемент как A, так и B в этих индексах в C, чтобы определить, какой из них требуется на основе 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.Y будет одинаковым в A и B для всех индексов; это может быть от 0 до 24. Поэтому, чтобы сделать длинное описание коротким, мне нужен алгоритм для заполнения C всеми возможными R-классами из A и B, где RY равны в обоих массивах, итерацией всех возможных комбинаций C и остановкой. когда тот первый экземпляр C проходит проверку CRC.

Звучит просто? Я надеюсь, что это так. Дайте мне знать, если вам нужны дальнейшие разъяснения, или укажите мне на ветку, в которой уже есть что-то похожее на это. ТИА

1 Ответ

0 голосов
/ 01 марта 2011

Я думаю, что вы подошли близко к ответу на свой вопрос.Создайте массив, в котором перечислены все индексы, которые вы должны попробовать A или B. L = {7,15,19} в примере.п = 3.Тогда вы будете цикл от 0 до 2 ^ n-1 включительно.На каждой итерации цикла вы будете проверять каждый бит b = 0, бит 1, ... вплоть до бита n-1.L [b] говорит вам, какой индекс вам нужно установить, и в зависимости от того, установлен ли бит, установите для него соответствующее значение A или B.

В худшем случае, хотя вам придется выполнить 2 ^24 комбинации с 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
...