Учитывая N-значное число из 3-х цифр, сгенерируйте все N-значные числа из 3-х основ, которые имеют k цифр, различающихся параллельным способом - PullRequest
Новая
       11

Учитывая N-значное число из 3-х цифр, сгенерируйте все N-значные числа из 3-х основ, которые имеют k цифр, различающихся параллельным способом

1 голос
/ 09 сентября 2011

Для решения моей проблемы естественно использовать базовые 3 числа. У меня есть несколько таблиц, проиндексированных по номерам оснований 3, и в какой-то момент мне нужно просмотреть все индексы, которые отличаются по k цифрам от заданного N-значного числа.

Например, если задано 120 в качестве 3-значного базового номера 3, числа, отличающиеся на 1 цифру, будут: 020 220 100 110 121 122

У меня есть некрасивый код, который делает это очевидным образом, но он медленен и его трудно распараллелить. Есть идеи, как это сделать эффективно?

(предпочитаемый язык: c ++)

Ответы [ 2 ]

0 голосов
/ 10 сентября 2011

Вот код в Mathematica . Документацию по отдельным командам можно найти в Центре документации Mathematica . 

digitReplacements[num3_, n_, k_] :=
 Module[{len, num, num3T},
  len = Max[{n, IntegerLength[num3]}];
  num = List /@ IntegerDigits[num3, 3, len];
  Flatten[
   ParallelTable[
    num3T = num;
    num3T[[ss]] = num3T[[ss]] /. {{0} -> {1, 2}, {1} -> {0, 2}, {2} -> {0, 1}}; 
    IntegerString[FromDigits[#], 10, len] & /@ Tuples[num3T],
    {ss, Subsets[Range[len], {k}]}
    ], 1
   ]
  ]

Разрез этого кода: 

  len = Max[{n, IntegerLength[num3]}];
  num = List /@ IntegerDigits[num3, 3, len];

Предполагая, что вы хотите включить числа с ведущими нулями, функция получает количество цифр (n) в качестве аргумента. Если вы этого не сделаете, разделение числа на отдельные цифры не будет генерировать n цифр, если у них начальные нули. Вторая строка преобразует число, подобное 2110, в список {{2}, {1}, {1}, {0}}. IntegerDigits выполняет расщепление и List /@ отображает List на полученные цифры, помещая дополнительные фигурные скобки, которые нам понадобятся позже. 

    num3T = num;
    num3T[[ss]] = num3T[[ss]] /. {{0} -> {1, 2}, {1} -> {0, 2}, {2} -> {0, 1}};

Некоторые из этих подсписков будут заменены (/. Является оператором замены, в котором участвуют замены, определяется списком позиций в сс) набором дополнительных трехзначных цифр, так что команда Tuples может сделать все возможные наборы из них. Например Tuples[{{1,2},{3},{4,5}}]-==> {{1, 3, 4}, {1, 3, 5}, {2, 3, 4}, {2, 3, 5}}

    IntegerString[FromDigits[#], 10, len] & /@ Tuples[num3T],

Tuples находится в конце строки. Первая часть - это чистая функция, которая воздействует на результат функции Tuples, чтобы снова превратить ее в число с помощью FromDigits и позаботиться о ведущих нулях, используя IntegerString (в результате получается строка, позволяющая для ведущих нулей).

Сердце - это создание таблицы этих кортежей, основанное на поиске всех возможных замещающих позиций. Это делается с помощью строки Subsets[Range[len], {k}], которая генерирует все подмножества списка {1,2, ..., n}, составленного путем выбора k чисел. ParallelTable циклически повторяет этот список, используя сгенерированные позиции для замены всех применимых цифр в этих позициях на списки возможных аналогов. Генерирование этого списка позиции смены цифр кажется естественным подходом для распараллеливания проблемы, поскольку вы можете посвятить части списка различным ядрам. ParallelTable - это вариант параллельных вычислений стандартной функции Mathematica Table, которая автоматически выполняет это распараллеливание.

Поскольку каждый набор позиций, который занимает ss, генерирует список результирующих чисел, конечный результат - это список списков. Flatten сводит это к одному списку чисел. 

digitReplacements[120, 3, 1]

==> {"010", "210", "100", "120", "111", "112"}

digitReplacements[2012, 5, 2]

==>{"10112", "11112", "20112", "21112", "12012", "12212", \
    "22012", "22212", "12102", "12122", "22102", "22122", "12110", \
    "12111", "22110", "22111", "00012", "00212", "01012", "01212", \
    "00102", "00122", "01102", "01122", "00110", "00111", "01110", \
    "01111", "02002", "02022", "02202", "02222", "02010", "02011", \
    "02210", "02211", "02100", "02101", "02120", "02121"}

digitReplacements[1220101012201010, 16, 6] // Length // Timing

==> {0.671, 512512}

Итак, мы находим полмиллиона подходов за 0,671 секунды. Если я изменю ParallelTable на Table, это займет 3,463 секунды, что примерно в 5 раз медленнее. Немного удивительно, так как у меня только 4 ядра, и обычно параллельные издержки поглощают значительную часть потенциального прироста скорости.

0 голосов
/ 09 сентября 2011

Звучит так, будто вы хотите, чтобы все комбинации имели одну цифру , а не одну бит ? 1 база 3 имеет 2 бита, отличных от 2 базы 3 (01 против 10).

Если это то, что вы хотите, вы можете распараллелить это, имея n рабочих потоков, где ваш номер имеет длину n цифр. Дайте каждой нити оригинальный номер и смещение цифры, которую вы хотите изменить. Поток должен вернуть два числа с измененной цифрой. Таким образом, в вашем примере поток 0 получит («120», 0) и вернется («121», «122»). Затем ваш главный поток получает все эти новые номера и добавляет их в список.

...