Генерация всех размещений без повторений рекурсивным способом

[Все темы по размещениям]

Теория: Окулов. Программирование в алгоритмах. 2004
Практика: K4.Размещения.(dl.gsu.by)

Представим, что нужно рассадить N гостей на M мест, при этом может получиться такая ситуация, что некоторые гости останутся стоять. Занумеруем всех гостей числами от 1 до N. А теперь давайте попробуем перечислить все возможные посадки. Пусть N = 4, а M = 3. Получаем:

1. 123
2. 124
3. 132
4. 134
5. 142
6. 143
7. 213
8. 214
9. 231
10. 234
11. 241
12. 243
13. 312
14. 314
15. 321
16. 324
17. 341
18. 342
19. 412
20. 413
21. 421
22. 423
23. 431
24. 432

Чтобы убедиться в том, что ни одна комбинация не была пропущена, найдем общее количество размещений по формуле A(M,N) = N! / (N-M)! = 4! / 1! = 24. Можно двигаться дальше.
Что касается самого принципа генерации, то он полностью совпадает с принципом генерации перестановок без повторений. Тем более, что если N = M, то будет происходить генерация всех перестановок без повторения.

1. int n,m;
2. string letters = "1234567";
3. vector<bool> usd;
4. string res;
6. void placement_lex(int pos) {
7.   if (pos == m) {
8.     printf("%s\n", res.c_str());
9.     return;
10.   }
11.   for (int i=0;i<n;++i) {
12.     if (!usd[i]) {
13.       usd[i] = true;
14.       res[pos] = letters[i];
15.       placement_lex(pos+1);
16.       res[pos] = ' '; // debug only
17.       usd[i] = false;
18.     }
19.   }
20. }
21. int main() {
22.     ...
23.   usd.resize(n);
24.   res.resize(m,' ');
25.   placement_lex(0);
26. }

* This source code was highlighted with Source Code Highlighter.

Решение: здесь

Размещения (placements)

Размещения без повторений
         Вопрос: “Сколькими способами можно разместить N гостей по M местам?” (N >= M)
         Правило: Порядок имеет значение, т.е. картежи {1,4,2} и {2,4,1} являются различными.
         Количество: A(M,N) = N * (N-1) * (N-2) * (N - M + 1) = N! / (N - M)!
1. Генерация всех размещений без повторений
     1.1. Рекурсивная генерация в лексикографическом порядке
          Практика: [K4.Размещения(dl.gsu.by)]
     1.2. Генерация следующего размещения в лексикографическом порядке(без перестановок) O(N*N)
          Практика: [K4.Размещения(dl.gsu.by)]
     1.3. Генерация следующего размещения в лексикографическом порядке(без перестановок) O(logN*N)
          Практика: [K4.Размещения(dl.gsu.by)]
     1.4. Генерация следующего размещения в лексикографическом порядке(с перестановками) O(N)
          Практика: [K4.Размещения(dl.gsu.by)]
     1.5. Генерация предыдущего размещения в лексикографическом порядке                  O(N)
          Практика: [K4.Размещения(dl.gsu.by)]
2. Генерация размещения по номеру L (задаются значения M и N)          O(N*N)
          Практика: [3784. Генерация размещений]
3. Получения номера по размещению (задаются значения M и N)            O(N*N) 
          Практика: [192. По размещению]

Размещения с повторениями
         Вопрос: “Сколько различных букетов можно собрать из K цветков, используя N видов цветов”
         Правило: Порядок имеет значение, т.е. картежи {1,1,5} и {1,5,1} являются различными.
         Количество: A(K,N) = N^K, где N - мощность алфавита, K - длина последовательности
4. Генерация всех размещений без повторений.
     4.1. Рекурсивная генерация в лексикографическом порядке
          Практика: [82. Все строки длины n из k различных символов]
     4.2. Генерация следующего размещения в лексикографическом порядке
          Практика: [82. Все строки длины n из k различных символов]
     4.3. Генерация предыдущего размещения в лексикографическом порядке
          Практика: [83. Все строки длины n из k различных символов в обратном порядке]
5. Генерация размещения по номеру L (задаются значения K и N)
6. Получение номера по размещению (задаются значения K и N)
7. Расстановка знаков в арифметическом выражении

задача Футурама (3298 на informatics.mccme.ru)

Условие
Эта задача показалась мне довольно интересной. Тем более, что она имеет схожие черты с другой очень хорошей задачей D++.

Итак, суть сводится к тому, что нужно упорядочить массив с учетом того, что последние два элемента гарантированно находятся на своих позициях. Элементы, находящиеся на позициях i и j запрещается менять местами, если ранее уже совершались обмены i-ого и j-ого элементов.
Из условия нам дают понять как можно обменять два элемента местами, используя два последних элемента. Пусть нужно обменять элементы 3 и 4, находящихся на позициях i и j:

Теперь нужно вспомнить, что исходный набор чисел является перестановкой. Это позволяет разложить имеющуюся перестановку на циклы и уже в дальнейшем работать с каждым циклом отдельно.
Понятно, что если упорядочить элементы в каждом цикле, то исходная перестановка станет единичной, т.е. упорядоченной.
В представленном решении не нужно помнить о запрещенных позициях для обменов, т.к. они все будут осуществляться через последние два элемента. Для любого цикла перестановки справедлив один из случаев:
1) Длина цикла равна 1. Понятно, элемент цикла находится на “нужном” месте в перестановке и ничего делать не нужно
2) Длина цикла равна 2. В данном случае элементы цикла можно обменять местами по правилу изложенному выше
3) Длина цикла больше 2. Это самый сложный случай. Рассмотрим перестановку A = {5,6,4,1,3,2,7,8}:

Один из циклов перестановки С = 1-5-3-4-1. Поставим на свои элементы цикла, отличные от двух последних(1 и 4), т.е. 5 и 3. Это можно сделать с помощью промежуточных обменов с предпоследним элементом перестановки:

Получилась перестановка B = {7,6,3,1,5,2,4,8}. Теперь немного отвлечемся и рассмотрим перестановку
A’={4,6,3,1,5,2,7,8}. Она имеет цикл С’ = 1-4, в то время, как элементы 3 и 5 находятся на “своих” местах. Для упорядочивания цикла C’ можно воспользоваться п.2)
Перестановка B получается из перестановки A’ после первого же обмена. Поэтому чтобы закончить п.3) необходимо выполнить оставшиеся 3 обмена, чтобы обменять в перестановке A’ элементы 1 и 4:

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

Решение

Contest list

В данном посте буду формировать список прорешенных контестов.

Div1:
1[+]. Московская командная олимпиада 2003
[15Jan12 - 17Jan12]     [Условие]
    A. Перегоны                    (алгоритм Флойда)
   $B. Сломанный калькулятор       (Теория чисел)
    C. Валютные махинации          (ДП-1) (* цифра после ДП означает уровень сложности: 1 – легкая)
    D. Двухтуровая олимпиада       (Моделирование)
    E. Черно-белые палиндромы      (Строки, Хеширование)
    F. Луч света в темном царстве  (Моделирование, Матрицы)
    G. Распаковка строчки          (Строки)
   *H. Дремучий лес                (Геометрия)
2[+]. Московская командная олимпиада 2004
[31Dec11-03Jan2012]     [Условие]
    A. Москва – сортировочная  (Поощрительная)
    B. Кафе                    (ДП-2)
    C. Euro-English            (Строки - муторные)
  $$D. D++                     (Моделирование. Цикл перестановки)
   $E. Скобки                  (ДП-2)
    F. Двоякие числа           (Поощрительная. Теория чисел)
   *G. OOO                     (Геометрия – 25 случаев)
    H. Калах                   (Моделирование)
    I. Сортировка масс         (Сортировка. Тип данных)
3[+]. Московская командная олимпиада 2005
[05Jan12 - 11Jan12]     [Условие]
    A. Результаты олимпиады      (Моделирование)
    B. Сокращение дроби          (GCD)
    C. Современники              (Сортировка. Моделирование)
   $D. Тройки чисел              (Теория чисел)
   $E. T2005(Sort)  T2005(Бор)   (Сортировка. Бинарный поиск / Бор)
    F. Роботы                    (Теория графов. Моделирование. Поиск в ширину. Битовая маска)
   $G. Монетки                   (Перебор. 2^30 > 3^15)
    H. Сверим часы               (Моделирование. Время)
   *I. Разрезанный прямоугольник (Геометрия)
   $J. Количество треугольников  (Арифметическая прогрессия)
4[+]. RROI–2012(Региональный этап всероссийской олимпиады школьников 2011-2012) 
[27Jan12 - 31Jan12]     [Условие]                                          [Разбор от М.Гуровица]
    A. Цапли                 (Поощрительная)
    B. Круглый стол          (Моделирование)
    С. Поврежденный XML      (Строки, Полный перебор) 
  $*D. Игра с числами        (Теория игр)
    E. Кондиционер           (Поощрительная)
    F. Космический кегельбан (Геометрия)
    G. Abracadabra           (Бор, Хеширование)


Div2(исходники и разборы только самых интересных задач):
1[+]. Московская индивидуальная олимпиада 7-9 класс (2006) [28Dec2011]
    С. Кинотеатр [второе решение]  (Мальчики/Девочки)
    E. Метро                       (Поиск в ширину) 
2[+]. Московская индивидуальная олимпиада 7-9 класс (2007) [28Dec2011]
    D. Кассы    (Время)
    E. Словарь  (ДП-2)
3[+]. Московская индивидуальная олимпиада 7-9 класс (2008) [19Jan2012]
    A. Автобусы (Моделирование. Мальчики/Девочки)
    D. Реклама  (Быстрая сортировка)
4[+]. Московская индивидуальная олимпиада 7-9 класс (2009) [26Dec2011]
    D. Изобретательный Петя (Строки. Хеширование) 
5[-]. Московская индивидуальная олимпиада 7-9 класс (2010)
6[+]. Московская индивидуальная олимпиада 6-9 класс (2011) [04Feb2012-10Feb2012]
   *D. Поход      (ДП-2)
   $E. Футурама   (Цикл перестановки) + [пост]

Tim Sort

[Все сортировки]

Теория: habrahabr.ru, код реальных мужиков на С (зеркало)

Практика: informatics.mccme.ru

Немного размышлений:
1) Не так давно общественность была взбудоражена малоизвестной сортировкой Tim Sort, которая творит чудеса. Поэтому возникло желание попробовать сделать ее реализацию. Когда разбирался в описании, представленном на хабре и в wikipedia, как в русской, так и в английской, возникли вопросы, на которые я не смог найти ответы. Больше всего вызывала вопросов та часть, в которой происходит эффективное слияние подмассивов, примерно равной длины. Т.к. я писал сортировку для случайного набора данных, поэтому хотелось избежать непоняток с волшебными длинами X,Y и Z, а именно просто сливать два последних подмассива, если они имеют одинаковую длину. Как показала практика в оригинальном алгоритме преследовалась та же идея.

Разбираясь в реализации на С(см. теория), было выведено правило грамотного слияния подмассивов с поддержанием баланса длин. Пусть X,Y,Z  - длины верхних трех интервалов, которые лежат в стеке. Причем X – это последний элемент стека.
Правило следующее:
1. Повторяем пока выражение (Z > X + Y && Y > X) не станет истинным
2. Если количество элементов в стеке не меньше 3 и Z <= X + Y – сливаем Y c min(X,Z).
   Иначе Если Y<=X – сливаем X c Y
3. Возвращаемся в п.1.

В wikipedia и на habr’e написано другое правило, в котором X и Z поменены местами, и по которому ничего путного сделать у меня не получилось.

2) В оригинальной идее предполагалось, что во временный массив помещается меньший из сливаемых подмассивов. При этом, если это левый подмассив, то формирование результирующего массива идет слева направо + используется бинарный поиск по не убыванию. В противном случае, когда правый подмассив имеет размер меньше чем левый, ответ формируется справа налево + используется бинарный поиск по не возрастанию. Скажу честно, мне было лень замачиваться на такие вещи, поэтому в приведенной реализации всегда копируется левый подмассив.

3) Для меня осталась загадкой, откуда у автора алгоритма Тима Петерсона такая любовь к сортировке вставками, которая требует в худшем случае n(n-1)/2 обменов. Хотя конечно, для худшего случая, когда массив упорядочен в обратном порядке, стоят нужные механизмы, которые реверснут массив за n/2 обменов, но все равно вопрос для меня остался открытым. В этом плане мне больше импонирует сортировка выбором, которая требует не более n обменов, которая и была приведена в реализации.

Реализация:

1. struct segment {
2.   int beg; // индекс первого элемента
3.   int len; // длина интервала
4.   segment(){}
5.   segment(int b, int l) : beg(b), len(l){}
6. };
7. // ответ должен быть в диапазоне (32,64]
8. inline int get_min_size(int n) {
9.   int r = 0;
10.   while (n >= 64) {
11.     n >>= 1;
12.     r |= n &1;
13.   }
14.   return n + r;
15. }
16. // Да простит меня Тим Петерсон, но вместо сортировки вставками
17. // я использую сортировку выбором
18. void selection_sort(vector<int> &mas, int beg, int last) {
19.   for (int i=beg; i<last;++i) {
20.     int min_pos = i;
21.     for (int j=i+1; j<last; ++j) {
22.       if (mas[j] < mas[min_pos])
23.         min_pos = j;
24.     }
25.     swap(mas[i],mas[min_pos]);
26.   }
27. }
28. const int dx = 1, dy = 2, dz = 3;
29. void merge(vector<int> &mas, vector<segment> &seg, bool isXY, vector<int> &tmp) {
30.   segment f = seg[seg.size() - dy];
31.   segment s = isXY ? seg[seg.size() - dx] : seg[seg.size() - dz];
32.   if (f.beg > s.beg) swap(f,s);
33.   int posF = 0, posS = s.beg, pos = f.beg-1;
34.   int lstF = f.len, lstS = s.beg + s.len;
35.   copy(mas.begin() + f.beg + posF, mas.begin() + f.beg + lstF, tmp.begin());
36.   int fAmount = 0, sAmount = 0;
37.   while (posF < lstF && posS < lstS) {
38.     if (tmp[posF] < mas[posS]) {
39.       mas[++pos] = tmp[posF++];
40.       ++fAmount; sAmount=0;
41.       if (fAmount == 7) {
42.         vector<int>::iterator it = upper_bound(tmp.begin() + posF, tmp.begin() + lstF, mas[posS]);
43.         copy(tmp.begin() + posF, it, mas.begin() + pos + 1);
44.         pos += it - (tmp.begin() + posF);
45.         posF += it - (tmp.begin() + posF);
46.       }
47.     }
48.     else {
49.       mas[++pos] = mas[posS++];
50.       fAmount=0; ++sAmount;
51.       if (sAmount == 7) {
52.         vector<int>::iterator it = upper_bound(mas.begin() + posS, mas.begin() + lstS, tmp[posF]);
53.         copy(mas.begin() + posS, it, mas.begin() + pos + 1);
54.         pos += it - (mas.begin() + posS);
55.         posS += it - (mas.begin() + posS);
56.       }
57.     }
58.   }
59.   copy(tmp.begin() + posF, tmp.begin() + lstF, mas.begin() + pos + 1);
60. }
61. void try_merge(vector<int> &mas, vector<segment> &seg, vector<int> &tmp, bool is_merge = false) {
62.   while (seg.size() > 1) {
63.     int x = seg[seg.size() - dx].len;
64.     int y = seg.size() < 2 ? 0 : seg[seg.size() - dy].len;
65.     int z = seg.size() < 3 ? 0 : seg[seg.size() - dz].len;
66.     if (seg.size() >= 3 && z <= x + y) {
67.       if (z < x) {
68.         merge(mas,seg,false,tmp);
69.         seg[seg.size() - dz].len += seg[seg.size() - dy].len;
70.         seg[seg.size()- dy] = seg[seg.size()- dx];
71.         goto POP_BACK;
72.       }
73.       else {
74.         merge(mas,seg,true,tmp);     
75.         seg[seg.size() - dy].len += seg[seg.size() - dx].len;
76.         goto POP_BACK;
77.       }
78.     }
79.     else if (is_merge || y <= x) {
80.       merge(mas,seg,true,tmp);
81.       seg[seg.size() - dy].len += seg[seg.size() - dx].len;
82.       goto POP_BACK;
83.     }
84.     else
85.       break;
86. POP_BACK: seg.pop_back();
87.   }
88. }
89. void tim_sort(vector<int> &mas) {
90.   int n = mas.size();
91.   vector<int> tmp(n);
92.   int min_size = get_min_size(n);
93.   int beg = 0, size = min_size;
94.   vector<segment> seg;
95.   seg.reserve((n-1)/min_size + 1);
96.  
97.   for (int i=0;i<n;i+=min_size) {
98.     size = min(min_size,n-i);
99.     selection_sort(mas,i,i+size); 
100.     seg.push_back(segment(i,size));
101.     try_merge(mas, seg, tmp);
102.   }
103.   while (seg.size() != 1) {
104.     try_merge(mas, seg, tmp, true);
105.   }
106. }

* This source code was highlighted with Source Code Highlighter.

P.S: Признаюсь я изначально не возлагал больших надежд на эту сортировку(особенно на свою эффективную реализацию), но должен признать, что был не прав. Данная реализация зашла за 0.061 с, в то время, когда быстрая работал за 0.059 с. Учитывая, что в данную реализацию можно добавить копирование меньшего подмассива + дописать бинарный поиск по не возрастанию, данная сортировка становится пожалуй лучшей для сортировки случайного набора данных. Разработчики Python не могли ошибаться =).