Как выполнить размещение k элементов из n?

Question

[Антон Барышев]

Здравствуйте! Необходимо создать изящный алгоритм для поиска размещения. А конкретно нужно выполнить размещение по 7 элементов из 8. Алгоритмы, которые я видел в интернете, работают с числовыми массивами, а у меня массив символов (char'ов). Все комбинации нужно сохранить, т.к. потом среди них будут проводиться выборки. Заранее спасибо.

Comments

[Wataru]

Пример приведите. Вам надо сгенерировать все размещения? Поиск какого-то конкретного?

[Антон Барышев]

Wataru, например, имеется массив символов { 'а' , 'л' , 'г' , 'о' , 'р' , 'и' , 'т' , 'м' }. Здесь 8 символов, мне нужно найти и записать в массив все размещения (в виде строки) по семь символов из этого массива. Например, "алгорит", "лгоритм", "алгоитм" и т.п. Сначала надо сгенерировать все возможные размещения, а потом искать делать выборки я буду делать уже сам по необходимым критериям.

[Wataru]

Антон Барышев, Уверены, что это хорошее решение вашей задачи? Может надо генерировать сразу удовлетворяющие вашим критериям размещения?

[Василий Банников]

Антон Барышев, вместо числового массива используйте массив из char. Потом преобразуйте его в строку.

[Антон Барышев]

Wataru, я был бы очень признателен, если бы вы поделились таким алгоритмом.

[Антон Барышев]

Василий Банников, я обязательно попробую.

[Василий Банников]

Антон Барышев,

Алгоритмы, которые я видел в интернете, работают с числовыми массивами

Так вы уже же нашли.
Чтобы в строку преобразовать - new string(charArray)

[Антон Барышев]

Василий Банников, да, спасибо. Люди выше уже написали об этом, что-то я не подумал о том, что char'ы тоже можно сравнивать. Сегодня попробую.

Answer 1

[Wataru]

Гуглите "алгоритм генерации размещений". Находится, например, это.

Работа с символами ничем не отличается от работы с числами. Во всех языках символы можно сравнивать по их кодам, и в алгоритмах кроме сравнения ничего нет.

Или можно сгенерировать размещения из {1,2,3,...N} а потом использовать эти числа в размещениях, как индексы символов. Надергайте из заданной строки символы по этим позициям и получите размещение из символов, а не чисел.

Answer 2

[Mercury13]

Будут повторы?
Если не будет — то достаточно отсортировать char’ы и использовать числовой алгоритм.
Если будут — ищите «размещения с повторами», и тоже сортируйте.