4

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

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

thanks in advance

bli
  • 41
  • 1
  • 5
  • 1
    Why C++ tag? Unless what you want is pure algorithmic. But you'll have to set rules anyway, even if you create the best IA ever which will auto-deduct a rule for each set. – Jaffa Sep 03 '12 at 20:40
  • thanks for your kind reminder, sorry for that. I just thought java and c++ are similar, maybe somebody in the c++ group can help me. – bli Sep 03 '12 at 20:48
  • 1
    I code in both java and C++, so trust me, they are very, VERY different. There is just a bit of syntax and some OOP notions that are the same :) – Jaffa Sep 03 '12 at 20:53
  • @bli what you want is a *partial order* – obataku Sep 03 '12 at 21:05

3 Answers3

2

One thing you can consider is swapping elements at random. You could pick a random position in your collection, then swap the element in that position with the next element. This way, you can prevent swapping 1 with 3, or 2 with 4. You can do this repetitively, until the numbers are properly scrambled:

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

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

elements are 1 and 3, so don't swap.

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

[2, 1, 4, 3] etc.

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

elements are 5 and 7, so don't swap.

if(7==5+2)continue; // ie don't swap.
  • after several times swap 1 will after 3, or 2 will after 4 – bli Sep 03 '12 at 20:55
  • 1
    @bli I don't understand what you mean. Could you elaborate? –  Sep 03 '12 at 20:56
  • after the edit it works, thanks a lot.The problem is :I have a sequence, for instance:1 2 3 4, I need to generalize all the sequence with the constraint(i must before i+2): e.g.1 must before 3, 2 must before 4 – bli Sep 03 '12 at 21:06
  • @bli I edited my answer, but I don't know if that will help you at all. Is that what you wanted? –  Sep 03 '12 at 21:13
0

If you use it as a string then you could use this answer's algorithm to swap all the numbers

When you enter all the numbers then just concatenate them together. There is no need to treat them as numbers or strings. All you want to do is reorder them.

When you get the result you could then check to see if your constraints match and then print out another list. Something like this perhaps

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 would work. For small input sets it shouldnt be too inefficient.

Community
  • 1
  • 1
RNJ
  • 15,272
  • 18
  • 86
  • 131
0

What you've defined here is known as a partial order. You wish to generate a random permutation which still satisfies the partial order, i.e. a random linear extension.

Luckily, the Java API specifies Collections.shuffle, which implements the Fisher-Yates algorithm to generate a random permutation. Unfortunately, the standard Java technique via Collections.sort is a comparison sort, and thus focused on total orders -- unlike the partial order we want. In fact, the Java API lacks a sorting algorithm we could use here.

One approach covered in "Generating Linear Extensions of Posets by Transpositions" involves that of swapping adjacent elements in the set in a fashion similar to Hassan's solution. This appears to be a functioning way for the localized problem at hand.

obataku
  • 29,212
  • 3
  • 44
  • 57