понедельник, 12 марта 2012 г.

Размещения (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) = NK, где 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. Расстановка знаков в арифметическом выражении

Комментариев нет:

Отправить комментарий