Генерация комбинаций / перестановок (t-наборы на символах v)

Я имею дело с покрывающими массивами, и мне нужно некоторое руководство по генерации наборов (с учетом определенных параметров) для вычисления того, является ли массив покрывающим массивом или нет.

Мне дали два входа для разбора — t а также v как целые числа. v содержит количество уникальных символов (целых чисел) в массиве. Это можно считать набором любых целых чисел. Целое число t представляет длину символов, которые я хочу получить из этого набора.

Так, например, предположим, v = 3 за {0,1,2} как символы и t = 2, Тогда я буду генерировать комбинации { (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), ..., (2,2) }, В общем, я буду генерировать v^t комбинации. Мне интересно, есть ли лучший алгоритм, чем тот, который я использовал, который может быть, возможно, дешевле в вычислительном отношении.

В основном то, что я делаю, — это подсчет на другой базе. Так, например, в приведенном выше примере я изначально начинаю с массива, который имеет t пробелы, выделенные для 0. На каждом проходе я увеличиваю младший значащий бит и преобразую его в набор или некоторую другую структуру данных для хранения моих комбинаций. Как только младший значащий бит переполняется, я устанавливаю его в 0 и увеличиваю следующий значащий бит. Это все считается в разных базах. Так что я бы закончил со следующим выводом для t=2 а также v=3:

00
01
02
10
11
12
20
21
22

Мой самый большой вопрос — это проблема перестановок или комбинаций? Я немного неясен в деталях между ними. Я считаю, что это перестановка только потому, что повторение происходит, и потому что порядок не имеет значения.

Аналогично, является ли этот алгоритм достаточно приличным, чтобы (потенциально) обрабатывать большие v? Мне дают параметр, который t будет 2 или 3, но v неизвестно Есть ли известный алгоритм для вычисления длиныt устанавливает на v символы? Для справки, я использую C ++ для этого.

0

Решение

Вы имеете дело с variations with repetitions, Есть много примеров, как на SO, так и по всему Интернету. Что касается вашего алгоритма, то его сложность будет, по крайней мере, соответствовать размеру выходных данных — на который вы уже указали — это будет Ω (v ^ t). Если побитовые операции работают для вас (т.е. соответствуют остальной части реализации), тогда да, вы можете сделать это таким образом.

2

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]