Перечисление всех возможных сочетаний (комбинаторика) C# - Помощь студентам

irene17 · 17.04.2014, 14:48

Необходимо перечислить все возможные сочетания (комбинаторика). Например: n=6, k=3. Тогда сочетания будут следующие:
123 134 146 236 345
124 135 156 245 346
125 136 234 246 356
126 145 235 256 456
Число n задается в начале работы программы, а значение k внутри программы меняется. Здесь как-то можно применить рекурсию, но не пойму как. Пишу на шарпе. Помогите решить.

Son Of Pain · 17.04.2014, 16:48

Самый простой способ: в цикле перебираешь все числа от 1 до (2^n)-1. Если количество единичных бит у числа равняется k - выводишь их номера, это и будет следующая комбинация.

irene17 · 17.04.2014, 18:06

Эта задача лишь часть программы. Значение n может быть достаточно большим, а в программе подобная процедура отыскания сочетаний выполняется приличное количество раз, нет ли метода требующего меньше времени выполнения?

Son Of Pain · 17.04.2014, 19:55

Цитата:

Сообщение от irene17

нет ли метода требующего меньше времени выполнения?

Есть, конечно ) тысячи их.
Выбирай в зависимости от дополнительных требований задания

phomm · 17.04.2014, 20:35

http://programmersforum.ru/showthread.php?t=138096
реализация метода с битами

irene17 · 18.04.2014, 13:41

Спасибо за помощь)

17.04.2014, 14:48	#1
irene17 Регистрация: 17.04.2014 Сообщений: 5	Перечисление всех возможных сочетаний (комбинаторика) C# Необходимо перечислить все возможные сочетания (комбинаторика). Например: n=6, k=3. Тогда сочетания будут следующие: 123 134 146 236 345 124 135 156 245 346 125 136 234 246 356 126 145 235 256 456 Число n задается в начале работы программы, а значение k внутри программы меняется. Здесь как-то можно применить рекурсию, но не пойму как. Пишу на шарпе. Помогите решить.

17.04.2014, 20:35	#5
phomm personality Старожил Регистрация: 28.04.2009 Сообщений: 2,899	http://programmersforum.ru/showthread.php?t=138096 реализация метода с битами My projects (Mirror) github telegram

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Комбинаторика - нахождение всех возможных комбинаций	chandrasecar	Общие вопросы Delphi	20	15.03.2014 11:57
Генерация всех возможных вариантов	NanaTich	Помощь студентам	6	23.05.2011 07:00
Комбинаторика. Получение возможных вариантов.	Alex Cones	Общие вопросы Delphi	3	16.01.2011 13:52
Перебор всех возможных вариантов	phenix	Помощь студентам	3	03.12.2010 21:29

17.04.2014, 16:48	#2
Son Of Pain Участник клуба Регистрация: 23.12.2010 Сообщений: 1,129	Самый простой способ: в цикле перебираешь все числа от 1 до (2^n)-1. Если количество единичных бит у числа равняется k - выводишь их номера, это и будет следующая комбинация.

17.04.2014, 18:06	#3
irene17 Регистрация: 17.04.2014 Сообщений: 5	Эта задача лишь часть программы. Значение n может быть достаточно большим, а в программе подобная процедура отыскания сочетаний выполняется приличное количество раз, нет ли метода требующего меньше времени выполнения?

18.04.2014, 13:41	#6
irene17 Регистрация: 17.04.2014 Сообщений: 5	Спасибо за помощь)