Задачка для программистов

[dil]

На входе: строчка из n букв (в основном, русских), например: “абук”, и дополнительное число m, например, 3.
Задача: сгенерировать из букв той строки ВСЕ возможные комбинации длиной m.

Количество этих комбинаций может быть достаточно велико: на первом месте одна из n букв, потом на втором одна из остальных n-1, потом одна из остальных n-2, и т.д.
Всего получается n!/(n-m)! . В вышеуказанном примере – 24 варианта, а если, например, 10 букв, из которых надо сгенерировать 5-буквенные комбинации, то их будет уже 30240.

Ну, я всё-таки довольно квалифицированный программист, поэтому вполне быстро написал эту програмку на питоне. Если кому интересно, могу показать. Но кто тут программисты, попробуйте сначала сами..

Оригинал этой записи в личном блоге.

Comments

[mopexod]

Вот за что я не люблю такие задачи - часто непонятно, что имелось в виду в условии.

Что значит "одна из n букв"?

Если буквы повторяются, скажем, на входе "аабук", то "ааб" - должно появиться на выходе? Или нет? Это разные "а" или одинаковые?

"бук" и "куб" - должны обе появиться?

[dil]

"одна из n букв" - в смысле, одна из букв, входящих в первоначальную строчку.

Да, если буквы повторяются, они могут совместно появляться на выходе - и "ааб", и "аау", и "аба", и "ака", и "каа", и т.д.

да, и "бук", и "куб", и "бак", и "каб", и всё остальное.

[mopexod]

Тогда рекурсия глубиной m, видимо, поможет. С передачей набора букв без уже использованной.

[dil]

Ну да, но вот как эту букву удалить, чтоб вызываемая функция её не использовала, но чтоб она показывалась в выходных строчках, а потом вернуть эту букву обратно, чтоб при последующих обработках, когда на этом уровне будет вынута другая буква, а эта могла бы использоваться на следующих уровнях

[mopexod]

Очевидное - делать новую корзинку с буквами для передачи вниз, и не класть в неё одну, текущую.

Видимо, более простое - параллельно с массивом букв держать массив bool, показывающий, доступна ли буква, или использована.
При итерации по массиву букв пропускать использованные. Перед передачей вниз - помечать текущую как использованную. ПОсле вызова рекурсии - помечать как доступную.

[dil]

Ну как-то так, да, остаётся это всё запрограммировать