Получение всех уникальных перестановок набора, заполненного двумя разными символами с ограничениями

Итак, я поискал и, честно говоря, не нашел решения.

Я совершенно потерялся, имея один из тех дней.

Допустим, у меня есть этот набор

string[] arr = { "N", "N", "N", "N", "O", "O", "O", "O" };

Я хочу найти все возможные уникальные перестановки, в которых никогда не бывает больше «O», чем «N» перед ним.

То есть, если по индексу [2], 1 "N" и 1 "O" уже были перед ним, то arr[2] должен содержать "N". ["N","O","N",...]

Я хочу написать функцию, которая может выводить 2D-массив всех перестановок, которые следуют этим правилам для набора любого размера.

Любая помощь будет принята с благодарностью.

Насколько большим может быть вход? Учитывая, что в любой момент существует только два типа ввода, у меня возникнет соблазн просто рассматривать каждую потенциальную перестановку как целое число (рассматривая ее в двоичном формате с N = 1 и O = 0 или наоборот) и просто прогонять все целые числа. в возможном диапазоне, чтобы увидеть, подходят ли они - но пока это будет только масштабироваться.

Jon Skeet 10.09.2018 10:42

@DaisyShipton, это была одна из моих первых мыслей, но чем больше я думал об этом, тем сложнее казалось. Какой шаблон циклов / итераций предоставит мне окончательный набор уникальных перестановок? Клянусь, сегодня мой мозг превратился в кашу.

MattyB 10.09.2018 10:47

Если есть дублирование, это не «набор»

Vladi Pavelka 10.09.2018 10:48

@VladiPavelka Извините за неправильную терминологию, думаю, я имел в виду только массив / группу. Любая помощь будет принята с благодарностью

MattyB 10.09.2018 10:51

@MattyB звучит как вопрос для интервью :) Я попробую

Vladi Pavelka 10.09.2018 10:56

Возможно, поможет stackoverflow.com/a/13891349/468973.

Magnus 10.09.2018 11:01

Если вы рассматриваете каждую возможную перестановку как целое число, перебрать их все тривиально: вы просто используете обычный цикл for от 0 до наивысшего значения (например, 255 в примере, так как на каждое значение приходится 8 бит). Затем вы должны убедиться, что в нем задано правильное количество бит и их позиции.

Jon Skeet 10.09.2018 11:45

Очень неудачный вопрос, закрытие: / Я был в процессе написания 2-страничного объяснения различных версий алгоритма решения и его алгоритмических сложностей

Vladi Pavelka 10.09.2018 11:52

@Vladi Pavelka Это известная проблема с многочисленными описаниями и анализами (каталонские числа). Если вы считаете, что у вас есть новая полезная информация, я могу попробовать открыть снова (не уверен, что это возможно)

MBo 10.09.2018 11:56
pastebin.com/ypQ9Erwm
Vladi Pavelka 10.09.2018 11:57

@MBo Я был просто разочарован, что меня отключили, но все в порядке :)

Vladi Pavelka 10.09.2018 12:03

@MattyB проверьте ссылку pastebin

Vladi Pavelka 10.09.2018 13:06

@VladiPavelka Спасибо! Я сейчас посмотрю. Спасибо, что нашли время пройти через это.

MattyB 12.09.2018 05:30

@MattyB добро пожаловать! :)

Vladi Pavelka 12.09.2018 17:40
0
14
67
0

Другие вопросы по теме