Алгоритм, чтобы я мог индексировать 2^n комбинаций таким образом, чтобы я мог отступать от любого значения индекса от 1 до 2^n без использования массива

Я пытаюсь что-то сделать, но это вне моего поля. Объяснение позволяет установить n = 3 для упрощения вещей, где n - общее число параметров в этом примере: A, B, C. Эти параметры могут иметь состояние ON и OFF (aka 0 или 1). Общее число комбинаций этих параметров равно 2^п = 8 в этом случае, который можно представить в виде:Алгоритм, чтобы я мог индексировать 2^n комбинаций таким образом, чтобы я мог отступать от любого значения индекса от 1 до 2^n без использования массива

Конечно, приведенный выше список может быть отсортирован в (2^п)! = 40320 способов. Я хочу алгоритм, чтобы я мог рассчитать состояние любого из моих параметров (0 или 1) с числом от 1 до 2^n. Например, если у меня есть число 3, используя приведенную выше таблицу, я знаю, что состояние A равно 1, а B и C равно 0. Конечно, вы можете иметь таблицу/массив, чтобы искать ее при определенной сортировке, но даже для относительно небольших значения n вам нужно иметь огромную таблицу.

Я не знаком с этим и методами, которые вы можете делать с индексацией, поэтому мне нужна помощь.

С уважением

источник

2016-06-19 TnF

Если вам не нужен точный порядок, указанный выше, он просто подсчитывается в двоичном формате. – melpomene

Хотя я не знаю конкретного ответа, вы, вероятно, должны искать что-то, связанное с «перечислением перестановок». Существует несколько способов генерации и/или вызова определенной перестановки (https://en.wikipedia.org/wiki/Permutation#Algorithms_to_generate_permutations). Но есть еще несколько шагов, чтобы заставить ее делать то, что вы хотите ... – viraptor

Мне не нужны точный список, я хочу, чтобы я мог вычислить состояние любого параметра для любого значения от 1 до 2^n, что требует согласованного метода индексирования. Я буду изучать это, но я не программист и не электрик/электронный инженер, поэтому любая информация ценится. – TnF

Только что понял, что вы действительно можете смотреть на него по-другому. Вы хотите использовать функцию шифрования N бит для другого набора из N бит. На практике это то же самое, что и format preserving encryption. Вопрос, вы заботитесь ли:

покрыты все 2^n случаев, или просто достаточно большое количество близко к 2^n (вы должны выбрать правильный шифрования/метод хеширования)
вы хотите сделать это в одностороннем или в обоих направлениях (т. е. вы когда-нибудь захотите спросить - у меня есть этот номер, соответствующий этому числу, которое я использую для перестановки)

Если ответ не соответствует обоим, вы можете просто найти FPE, который не требует создания всей таблицы (некоторые делают).

источник

2016-06-19 01:34:01 viraptor

Спасибо за ответ, но я думаю, что вы неправильно поняли проблему. Было бы очень сложно объяснить, чего я пытаюсь достичь здесь, но двоичный подсчет является очень хорошим решением для моего случая, поскольку для любого n массив комбинаций, который будет сгенерирован, всегда будет одинаковым, и его легко получить состояние каждого параметра, назначая каждому параметру определенную цифру двоичного числа. В приведенном выше примере, если вы установили 1-ю цифру в A, от 2-го до B и т. Д., То для любого десятичного числа 2^n-1 я получаю индивидуальную двоичную цифру n разного значения, которая соответствует любому n :) – TnF

Я видел еще одну проблему finding all subsets of a given set using bitmask. Вы можете использовать ту же концепцию в своем случае. Это link содержит хороший учебник.

источник

2016-06-19 01:39:13 Prince

да, это в основном то, Я пытаюсь сделать это просто индексирование, это моя проблема, а не создание набора. Хорошие ссылки, хотя бинарный счет, как упоминалось в Мельпомене, является решением моей проблемы :) – TnF

Алгоритм, чтобы я мог индексировать 2^n комбинаций таким образом, чтобы я мог отступать от любого значения индекса от 1 до 2^n без использования массива

ответ

Смежные вопросы