Algorithm for generating permutations while preserving the order of elements in groups

Question

Software testing

Hello! I ran into a problem that I can not compose the algorithm I need, so I turn to you.

The situation is this. There is a very tricky data structure, there are three operations:

• create
• set
• delete

I am writing a unit test for this structure. It would be desirable to sort out all possible variants of sequences of calls of these operations. But, it is clear that you first need to create a record, then change it, and only then delete it.

Let's say we have three elements (but I would like for an arbitrary number). Those. some of the following permutations are possible:

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

Etc.

How to implement it? The language is not important, even in pseudocode. I just don't know which direction to go.

Thanks in advance.

Answer 1

If I understand you correctly, you can use the generator of all permutations with repetitions on the following set:
Number of elements = number of records being tested (3 in your example)
Number of repetitions of each element = 3 (add, change, delete).
And then just for each repetition of the element (there are three of them), from left to right, put down “create” “change” “delete”.
But there is a problem here - you cannot test the "create" "delete" chains - for this you need to generate a bunch of possible permutations.
In general, firstly, you are testing only correct behavior in this way, without checking what will happen with erroneous calls.
Second - IMHO (based on the information provided), your approach is not entirely correct, you need to break the code into modules and test everything with only one element, and write tests for the fact that if there are several elements, there are no overlaps (i.e. working with they are conducted independently).

Answer 2

And for testing “create” / “delete”, you need to add a random number with a probability of 1/2, depending on the value of which, either use “set” or throw out the second of the occurrences altogether.

Answer 3

Cool puzzle :) It looks like you gave an example of a context-sensitive language (if you take it in a general way). There will be a lot of combinations. If I'm not mistaken (k*n)!/ (k!)^n where n is the number of groups, k is the number of elements in each group. For example, for three groups with three elements <c1, s1, d1>, <c2,s2,d2> <c3, s3, d3> there will be 9!/3!3!3 combinations! = 1680.0