Shuffling an ArrayList until conditions are fulfilled (Java)

Question

First, I'm not a native English-speaker so please forgive me some errors and mistakes.

I want to shuffle an ArrayList (no problem there), but after the shuffling the list has to fulfill certain conditions. My first approach was to create if-statements and shuffle everytime they are true. But there are so many conditions, I don't know how to properly link them.

Example: I have an ArrayList with these integers:

0, 1, 2, 3, 4, 5, 6

Conditions after shuffling:

• an even number can't follow an even number, unless it's 6.
• 6 can be placed wherever.
• Also e.g. 0 can't be followed by 1, so the next possible number would be 3, 5, or 6. (
• Same for e.g. 1. 1 can be only followed by 0, 4 or 6.

Every element in the ArrayList should only be listed once, that is why I thought shuffling would be the easiest way to create a new List.

Am I thinking wrong? Is there an easier way? I'm fairly new to programming... Thanks in advance for any answers or suggestions.

EDIT: Here are all conditions:

• The list has to start with an even number (preferably not by 6, but that doesn't really matter)
• an even number can't be followed by another even number
• a number can't be followed by the next closest one (1 can't be followed by 2, only 0, 4 or 6)
• as said before: 6 can be placed wherever
• The shuffled List could be something like this: 0, 3, 6, 5, 2, 1, 4

Well I think that's all.

If I want to create multiple if-statements, my main problem is to figure out the proper way to link them effectively (so that every if-statement is considered).

Answer 1

The shuffling approach is no good, for two reasons:

1. There may ne no solution, hence your program would shuffle until end of all time.
2. It will get quite time consuming as the number of elements change.

I suggest another solution:

• We are given a set of numbers (may be represented by a list)
• We need a boolean function canFollow that returns true if a given number may extend the result list we have so far. (The rules you have given would allow an easier function that takes two numbers, but for more complex conditions like 5 can be followed by 8 only when not preceded by 6 the more general function would work.)
• Once you have this, you can construct a solution: Start out with an empty list. While the given set is not empty, take one element from it, and check if it can follow the result. If so, repeat until the given set is empty, in which case you have a solution. Otherwise, try the next number:

In pseudo code:

List<Int> brute(List<Int> result, List <Int> given) {
    if (given is empty) return result;
    foreach i in given
        if i can follow result
            r = brute(result + i, given - i)
            if r != null return r
    return null
}
solution = brute([], [1,2,3,4,5,6])

(Note that result + i is short for result with i appended and given - i is given without i, but make sure you construct this without destryoing the original result and given.)

If you need all solutions, this can easily be changed by adding a valid result to some list that starts out empty.

Answer 2

Assuming you have a requirement that all possible outcomes are equally likely then the only simple approach is going to be to brute-force create all combinations and then select randomly from that. All combinations is 7! == 7*6*5*4*3*2*1 == 5040 combinations which isn't many really. For a much larger number I wouldn't recommend this approach though.

List<int[]> valid = new ArrayList<>(5040);

recursiveBuild(valid, new int[] {}, new int[] { 0,1,2,3,4,5,6));

Where recursiveBuild is:

void recursiveBuild(List<int[]> valid, int[] soFar, int[] remaining) {

    if (remaining.length == 0) {
       // Check the whole thing is valid - can maybe skip this check
       // if the character-by-character check covers everything
       if (isValid(soFar)) {
          valid.add(soFar);
       }
    } else {
       for (int i=0;i<remaining.length;i++) {
           int[] newSoFar = new int[soFar.length+1];
           for (int j=0;j<soFar.length;j++) {
               newSoFar[j]=soFar[j];
           }
           newSoFar[newSoFar.length-1]=remaining[i];

           int[] newRemaining = new int[remaining.length-1];
           for (int j=0;j<newRemaining.length;j++) {
               if (j>=i) {
                   newRemaining = remaining[j+1];
               } else {
                   newRemaining = remaining[j];
               }
           }

           // Only continue if the new character added is valid
           if (isValid(newSoFar, newSoFar.length-1)
               recursiveBuild(valid, newSoFar, newReamining);
       }
    }
}

To solve the actual problem you listed I would use a variant on the strategy pattern, defining each rule as its own object (in Java 8 closures will make this much less verbose):

interface CheckCondition {
    boolean passesCondition(int index, int[] arr);
}


CheckCondition[] conditions = new CheckCondition[] {
    new CheckCondition() {
         @override
         public boolean passesCondition(int index, int[] arr) {
             // The list has to start with an even number
             return index!=0 || arr[index]%2==0;
         }
    },
    new CheckCondition() {
         @override
         public boolean passesCondition(int index, int[] arr) {
             // an even number can't follow an even number, unless it's 6.
             return index==0 || arr[index]==6 || arr[index]%2==1 || arr[index-1]%2==1;
         }
    },
    new CheckCondition() {
         @override
         public boolean passesCondition(int index, int[] arr) {
             // a number can't be followed by the next closest one unless its 6
             return index==0 || arr[index]!=arr[index-1]-1 || arr[index]==6;
         }
    },
};

Now use those rules to check validity:

boolean isValid(int[] arr, int index) {
   for (CheckCondition c: conditions)
      if (!c.passesCondition(arr.length-1, arr)
          return false;
   return true;
}

boolean isValid(int[] arr) {
   for (int i=0;i<arr.length;i++) {
       if (!isValid(arr, i);
           return false;
   }
   return true;
}