2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Комбинаторика (размещения, сочетания, генерация перестановок
Сообщение19.05.2007, 15:07 
У меня вот такой тупой вопрос: в чем различие размещений и сочетаний? :)

Например, в справочнике Бронштейна увидел две задачи:
Цитата:
1 . В турнире принимают участие 8 команд. Сколько различных предсказаний относительно распределения трех первых мест по результатам соревнований можно сделать?

2. Сколькими способами можно из множества k (различных) элементов выбрать r элементов?


Первая относится к размещениям, вторая к сочетаниям. Но я разницы не вижу :(
Для меня первая задача все равно что "сколькими способами можно из 8 команд выбрать 3 команды?".

 
 
 
 
Сообщение19.05.2007, 15:18 
Аватара пользователя
В первой задаче Вы должны не только выбрать 3 команды, но и сказать, какая займет первое место, какая - второе, какая - третье. Т.е. здесь учитывается порядок. Во второй задаче порядок не важен, про каждый элемент множества важно только - выбран он или нет.

 
 
 
 
Сообщение19.05.2007, 15:49 
:) Ясно, спасибо.

Еще кое-что: например, мне нужно получить все варианты перестановок из символов 'A', 'B' и 'C':
Цитата:
ABC
ACB
BAC
BCA
CAB
CBA


Если забить все символы в массив, т.е.
$array = array("A", "B", "C");
То получим следующее (индексы элементов):
Цитата:
012
021
102
120
201
210


Я заметил, что разность каждой последующей перестановки индексов массива с текущей всегда кратна 9.
Причем, с любым кол-вом символов. Если взять 'A', 'B', 'C', 'D', то получится тоже самое:
Цитата:
0123
0132
0213
0231
...


Вы не подскажите каким образом лучше получить все возможные варианты и почему разность всегда кратна 9? Нельзя ли этим воспользоваться? :)

 
 
 
 
Сообщение19.05.2007, 23:14 
Unkind писал(а):
Вы не подскажите каким образом лучше получить все возможные варианты и почему разность всегда кратна 9? Нельзя ли этим воспользоваться?

Дело в том, что в число, записанное в десятичной системе счисления имеет такой же остаток при делении на 9, что и сумма его цифр. Поэтому разность двух чисел, с одинаковым набором цифр в десятичной записи, делится на 9.

Для получения всех перестановок можно, например, использовать индуктивную процедуру. То есть, пусть $n!$ перстановок из $n$ элементов уже построены. Тогда для каждой такой перстановки строим $n+1$ перстановку с новым элементом.

 
 
 
 
Сообщение21.05.2007, 21:12 
neo66 писал(а):
Тогда для каждой такой перстановки строим $n+1$ перстановку с новым элементом.

Не понятно. Что это дает? Не могли бы Вы привести пример? Извините, если я так туплю...

 
 
 
 
Сообщение21.05.2007, 22:10 
Аватара пользователя
Unkind писал(а):
мне нужно получить все варианты перестановок


Генератор перестановок на языке АЛГОЛ-60. Переведите на любой современный язык программирования и пользуйтесь.

Код:
procedure perm(n) dataresult:(x);
         value n; integer n; array x;
begin real t;integer k,q; own integer array p,d[2:n];
         if prim115 then
           begin prim115:=false;
             for k:=2 step 1 until n do
               begin p[k]:=0; d[k]:=1 end k
           end prim115;
         k:=0
index:   p[n]:=q:=p[n]+d[n];
         if q=n then
           begin d[n]:=-1; go to iter end;
         if q≠0 then go to trans;
         d[n]:=1; k:=k+1;
iter:    if n>2 then
           begin n:=n-1; go to index end iter;
         q:=1; prim115:=true;
trans:   q:=q+k;t:=x[q];
         x[q]:=x[q+1];x[q+1]:=t
end perm;


Массив x, содержащий не менее n элементов, содержит текущую перестановку и не должен изменяться между обращениями к процедуре. При каждом обращении процедура вычисляет следующую перестановку.
Глобальная переменная prim115 при первом обращении должна иметь значение true. После первого обращения она принимает значение false и сохраняет это значение до конца n!-го обращения к процедуре perm. К этому моменту массив x восстанавливается в первоначальном порядке, а prim115 принимает значение true.
Описатель own определяет локальные величины, которые сохраняются при выходе из процедуры, и при следующем входе процедура может использовать значения, полученные при предыдущем обращении.

М.И.Агеев, В.П.Алик, Ю.И.Марков. Библиотека алгоритмов 101б - 150б. Москва, "Советское радио", 1978.

 
 
 
 
Сообщение22.05.2007, 16:41 
Unkind писал(а):
neo66 писал(а):
Тогда для каждой такой перстановки строим $n+1$ перстановку с новым элементом.

Не понятно. Что это дает? Не могли бы Вы привести пример? Извините, если я так туплю...

Пусть у нас есть перестановка из трех элементов (A,B,C) и элемент D. Тогда получаем 4 новые перестановки из 4 элементов:
(DABC), (ADBC), (ABDC), (ABCD).
И точно также поступаем с каждой 3-перстановкой.

 
 
 
 
Сообщение24.05.2007, 22:14 
Someone, спасибо огромное, работает :)

neo66, все, понял, тоже спасибо :)

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group