Алгоритм перестановки в виде

Question

R= repeats allowed -> 2
A= alphabet (1-10)
S= space = 4;

Итак, мы хотим пример:

[1][1][4][5]
[1][7][4][5]
[5][1][4][5]

Но нужна математическая формула для вычисления этой и всех комбинаций?

Answer 1

Насколько я понимаю, ваш алфавит составляет 1 ... 10, каждая буква может встречаться дважды. Так что у вас действительно есть алфавит, который ...

1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10

Длина 20, а не 10.

Теперь проблема становится 20 перестановками 4.

Надеюсь, это поможет.

EDIT: В соответствии с вашими дополнительными комментариями к вашему вопросу вы можете проверить каждую сгенерированную перестановку, чтобы увидеть, имеет ли она форму XXYY, поскольку она будет недействительной в соответствии с написанным вами.

Answer 2

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

Есть два случая:

• Перестановки, не содержащие дубликатов. Это просто 10 P 4
• Перестановки, содержащие ровно один дубликат:
  • Выберите номер дубликата: 10 C 1
  • Выберите для нее два места: 4 C 2
  • Выберите числа, которые вписываются в оставшиеся два места: 9 P 2

Таким образом, ответ на этот конкретный случай 9360.

Answer 3

Общее количество
N * [(S выбрать 1) * ((N-1) переставить (S-1)) + (S выберите 2) * ((N-1) перестановка (S-2)) + ... + (S выбрать R) * ((N-1) переставить (S-R))]

• Другими словами, вероятно, лучше всего исправить 1 на месте повторяющегося предмета (S choose 1 разные способы выполнения это) и переставить оставшиеся N-1 предметы над S-1 оставшимися пробелами; (как обычно N permute S)

• затем исправьте 2 ваших идентичных предмета в место (S choose 2 разные способы делать это) и переставлять оставшиеся N-1 предметов на оставшихся S-2 местах.

• и т. Д. Для каждого возможного количества повторяющихся элементов от 1 до R

• И тогда есть N вариантов для Ваш возможный повторный предмет.

Вы также можете использовать этот алгоритм для перечисления возможностей.

Редактировать

О, дорогой. Спасибо @blueraja, вы абсолютно правы! случай n-повторяющихся предметов не обобщается на 1 предмет!

исправленная формула поэтому

(N permute S)
+ N * [ (S choose 2) * ((N-1) permute (S-2)) 
      + (S choose 3) * ((N-1) permute (S-3)) 
      + ... 
      + (S choose R) * ((N-1) permute (S-R)) ]

Answer 4

Это хорошая статья о комбинациях и перестановках, там вы найдете все формулы

Answer 5

Я предполагаю, что только один элемент может повторяться, и этот элемент не является предопределенным.

Вот формула, которая работает с A (размер алфавита), S (размер строки) и R (максимальное количество повторений):

f (A, S, R) = (A perm S) + A Сумма [r = 2 до R] ((S выбирает r) (A-1 perm Sr))

Например, для R = 1 (простая перестановка) мы получаем f (A, S, R) = (A perm S), как и ожидалось. Для A = S = R = 2 имеем f (A, S, R) = 4, что соответствует:

1,2

2,1

1,1

2,2

Случай, который вы описываете в вопросе: A = 10, R = 2, S = 4, и тогда мы имеем:

f (A, S, R) = 9360

(точно так, как рассчитал BlueRaja)

Answer 6

Существует относительно немного возможных решений (

OR

• Генерация (упорядоченных) комбинаций из N различных слов

• Генерация перестановок этого подмножества, чтобы получить все возможности без дубликатов

• Сделайте то же самое с N-1 словами

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