Комбинаторика (размещения, сочетания, генерация перестановок

[Unkind]

У меня вот такой тупой вопрос: в чем различие размещений и сочетаний?

Например, в справочнике Бронштейна увидел две задачи:

Цитата:

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

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

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

[PAV]

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

[Unkind]

Ясно, спасибо.

Еще кое-что: например, мне нужно получить все варианты перестановок из символов '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? Нельзя ли этим воспользоваться?

[neo66]

Unkind писал(а):

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

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

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

[Unkind]

neo66 писал(а):

Тогда для каждой такой перстановки строим $n+1$ перстановку с новым элементом.

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

[Someone]

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.

[neo66]

Unkind писал(а):

neo66 писал(а):

Тогда для каждой такой перстановки строим $n+1$ перстановку с новым элементом.

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

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

[Unkind]

Someone, спасибо огромное, работает

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