Алгоритм генерации перестановок с сохранением порядка элементов в группах

Question

[Александр Рулёв]

Здравствуйте! Столкнулся с проблемой, что не могу составить необходимый мне алгоритм, поэтому обращаюсь к вам.

Ситуация такая. Есть очень хитрая структура данных, есть три операции:

• create
• set
• delete

Я пишу юнит-тест для этой структуры. Хочется перебрать все возможные варианты последовательностей вызовов этих операций. Но, понятно, что сначала нужно создать запись, затем изменить её, и только потом удалить.

Допустим, количество элементов у нас три (но хотелось бы для произвольного количества). Т.е. возможны какие-нибудь такие перестановки:

• create1 create2 set1 delete1 create3 set2 set3 delete3 delete 2
• create1 set1 create2 create3 delete1 set3 delete3 set2 delete 2

И так далее.

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

Заранее спасибо.

Answer 1

[VenomBlood]

Если я правильно вас понял — можно использовать генератор всех перестановок с повторениями на следующем множестве:
Количество элементов = количеству тестируемых записей (3 в примере у вас)
Количество повторений каждого элемента = 3 (добавить, изменить, удалить).
И потом просто для каждого повторения элемента (их три) слева направо проставить «создать» «изменить» «удалить».

Но тут есть проблема — вы не можете протестировать цепочки «создать» «удалить» — для этого надо генерировать еще кучу возможных перестановок.

А вообще, во первых — вы так тестируете только корректное поведение, не проверяя что будет при ошибочных вызовах.
Второе — ИМХО (исходя из представленной информации) у вас подход не совсем верен, надо разбить код на модули и протестировать все только с одним элементом, и написать тесты на то, что при наличии нескольких элементов не происходит накладок (т.е. работа с ними ведется независимо).

Comments

[Александр Рулёв]

О, отлично, то что нужно, спасибо.

Ошибочные вызовы я проверяю отдельно.

А по поводу второго я даже не знаю. Дело в том, что данные располагаются в памяти довольно хаотично и неудачное стечение обстоятельств может испортить чужие данные. Хотелось бы рассмотреть все возможные варианты. Причём, даже при вот таком вот тестировании всех возможных порядков рассматривается лишь какая-то область вариантов. В общем, буду думать, может позже что-нибудь придумается, в данный момент это просто прототип.

[Александр Рулёв]

for (List<Integer> elements : Collections2.orderedPermutations(Arrays.asList(0, 0, 0, 1, 1, 1, 2, 2, 2))) {
    System.out.println(elements);
}

Если кому-нибудь понадобиться такое на Java, то метод orderedPermutations из библиотеки гугла Guava делает как раз то, что нужно.

Answer 2

[Андрей]

А для тестирования «создать»/«удалить» нужно добавить случайное число с вероятностью 1/2, в зависимости от значения которого либо использовать «set» либо выбрасывать второе из вхождений вообще.

Answer 3

[lightcaster]

Крутая задачка :). Похоже вы привели пример контекстно-зависимого языка (если взять в общем виде). Комбинаций будет очень много. Если не ошибаюсь (k*n)!/ (k!)^n где n — кол-во групп, k — кол-во элементов в каждой группе. К примеру, для трех групп с тремя элементами <c1, s1, d1>, <c2,s2,d2> <c3, s3, d3> комбинаций будет 9!/3!3!3! = 1680.0