Generate random order but with restriction in java

Question

When I put an integer list, how can I generate another random order, but with a restriction?

For example, I put the integer 1, 2, 3, 4 in the collection, and when I try to print the result, for example, "1 2 3 4", "1 2 4 3", "1 3 2 4", 2 1 3 4 " or "2 1 4 3" (1 must be up to 3, 2 must be up to 4)

early

Answer 1

One thing you can consider is the random selection of items. You can select a random position in your collection, and then change the element in this position to the next element. Thus, you can prevent the exchange from 1 to 3 or 2 to 4. You can do this again until the numbers are correctly scrambled:

[1, 2, 3, 4] random number is 0, swap with the element at position 1.

[2, 1, 3, 4] random number is 1, swap with the element in position 2.

elements 1 and 3, so do not change them.

[2, 1, 3, 4] random number is 2, swap with the element in position 3.

[2, 1, 4, 3] , etc.

If you want to generalize the constraint, you can simply change this condition. Instead of refusing to exchange when elements 1 or 3, or 2 and 4 (as in the example above), you can make sure that the two elements in the positions to be exchanged are not within 2 of each other, so something like if(b==a+2)continue; :

elements are 5 and 7, so do not change them.

 if(7==5+2)continue; // ie don't swap. 

Answer 2

If you use it as a string, you can use this response algorithm to exchange all numbers

When you enter all the numbers, just combine them together. There is no need to consider them as numbers or strings. All you want to do is reorder.

When you get the result, you can check if your limits match, and then print another list. Something like this is possible

 private boolean isConstraintSatisfied(String wholeString, String firstNum, String secondNum){ return wholeString.indexOf(firstNum) <= wholeString.indexOf(secondNum); } 

Not the most elegant solution, but I think it will work. For small input sets, it should not be too inefficient.

Answer 3

What you have defined here is called partial ordering . You want to create a random permutation that still satisfies a partial order, i.e. a random linear extension.

Fortunately, the Java API specifies Collections.shuffle , which implements the Fisher-Yate algorithm to generate a random permutation. Unfortunately, the standard Java method using Collections.sort is sorting and thus focuses on general orders - unlike the partial order we want. In fact, the Java API does not have a sorting algorithm that we could use here.

One approach discussed in “Creating Posets Transposition Linear Extensions” involves replacing adjacent elements in a set in a style similar to the Hassan solution. This seems to be an effective way for a localized problem.