Shuffling Help

[KnivesACE]

I have a bit of a problem. I'm trying to create a program that takes a user defined integer from the command line N and shuffles the integer from 0 through N.

The problem I have, is that the integers must not follow each other. Meaning, 4 does not follow 5, and 8 does not follow 7. I've created the program so that it shuffles the integers, then prints them out. However, I cannot seem to figure out the trouble I am having. Any help would be appreciated.

code:

public class Shuffle {     public static void main(String[] args) {         int N = Integer.parseInt(args[0]);                 int[] song = new int[N];         for (int position = 0; position < N; position++) {             int list = position;             song[position] = list;         }         for (int current = 0; current < N; current++) {             int swap = current + (int) (Math.random() * (N - current));             int tempSong = song[current];             song[current] = song[swap];             song[swap] = tempSong;             System.out.print(song[current] + " ");         }         System.out.println();     } }

This is an example of what it currently prints out.

code:

java Shuffle 10 2 1 3 8 6 7 9 0 4 5

I would need to fix it so that 2, doesn't follow or come before 1. 6 before or after 7, etc.


Thanks!

[Insectoid]

How can 2 not follow or precede 1? The only option left is for them to be simultaneous. 1 and 2 at the same time. in a list, a number is always before or after another number, unless it is a one term list.

[wtd]

Just a bit of a suggestion on how OOP can make your main method a bit more elegant. Keep in mind I am currently rebuilding my system, and without a Java compiler, so this may or may not work. It has not been tested.

Java:

import java.util.List; import java.util.ArrayList; interface Initializer<T> {     public T value(int n); } class SwappableElementsList<T> {     private List<T> list;     public SwappableElementsList(int n, Initializer<T> init) {         list = new ArrayList<T>(n);         for (int i = 0; i < n; i++) {             list.set(i, init.value(i));         }     }     public void swap(int a, int b) {         T temp = list.get(a);         list.set(a, list.get(b));         list.set(b, temp);     }     public T get(int position) {         return list.get(position);     } } public class Shuffle {     public static void main(String[] args) {         final int N = Integer.parseInt(args[0]);         final SwappableElementsList<Integer> song =             new SwappableElementsList<Integer>(N, new Initializer<Integer>() {                 public Integer value(int n) {                     return n;                 }             });         for (int current = 0; current < N; current++) {             int swap = current + (int)(Math.random() * (N - current));             song.swap(current, swap);             System.out.print(song.get(current) + " ");         }         System.out.println();     } }

[jbking]

This is a rather tricky problem since you have to keep an eye on both what values you are using, but also which values remain. For example, there are only a couple of solutions for N = 3:

1 3 0 2 and its reverse 2 0 3 1

Notice that for 1 or 2, you don't have a couple of options for what would be on either side as 1 would only have 3 allowed to be next to it and for 2 there is only 0 that can be adjacent to it.

I do have the questions of whether any wrapping has to be accounted for, e.g. does the first and last position have to also be non-adjacent what about 0 and N?

[KnivesACE]

Sorry, maybe I should have been a little clearer. The numbers cannot be in a sequential pair. They can come after or before one another, however they cannot be NEXT to each other. Ie: The order can go 0 3 5 2 4 1, however it cannot go 0 2 3 5 4 1 because 2,3 are sequential pairs, and 5, 4 are sequential pairs.

And no, wrapping does not have to be accounted for. I guess the easiest way you can think of this is as a shuffle program for music. You don't want the 3rd and 4th song to play one after another.

[S_Grimm]

use if else statements

Java:

if (numbertoprint == ((nextnumber + 1) ||(nextnumber -1)) {      randomize nextnumber } else { System.out.println (nextnumber) }

That seems to be the easy way to me.....

[jbking]

A/V, there is one small issue with that:

What if the shuffle ends up backed into a corner. For example, if N=10 and the first few values are the following:
4 6 0 8 5 7 9

The 3 values left are 1,2, and 3.

Alternatively, when there are only a few values left, there may be the case where care has to be taken to ensure that the condition of non consecutive numbers holds. So, in my example above, if that 9 is taken out and any of the other 3 values are used there is still a solution using any of the other 3 values:
3 1 9 2
1 3 9 2
2 9 1 3
2 9 3 1

So there is the challenge of ensuring the last few values will have a solution. I like these kinds of puzzles.

[KnivesACE]

I'm not sure if I'm doing something wrong with what you said A/V.

When I compile, it gives the the following error:

Java:

MusicShuffle2.java:23: ']' expected                 { randomize song[swap]; }                                  ^ MusicShuffle2.java:23: illegal start of expression                 { randomize song[swap]; }                                      ^ 2 errors

Java:

int N = Integer.parseInt(args[0]);         int M = Integer.parseInt(args[1]);                         int[] song = new int[N];         for (int position = 0; position < N; position++) {             int list = position;             song[position] = list;             }         //Shuffle them up.         for (int current = 0; current < N; current++) {             //Select the position of the song to swap.             int swap = current + (int) (Math.random() * (N - current));             //Remember the current song.             int tempSong = song[current];             song[current] = song[swap];             song[swap] = tempSong;             if (song[current] == ((song[swap+1]) || (song[swap]-1)))                 { randomize song[swap]; }             else                 { System.out.println(song[swap]); }                                      System.out.println(song[current] + " ");         }

[wtd]

Bad:

code:

song[current] == ((song[swap+1]) || (song[swap]-1))

[KnivesACE]

wtd @ Tue Oct 21, 2008 11:30 am wrote:

Bad:

code:

song[current] == ((song[swap+1]) || (song[swap]-1))

Yeah, I saw that when I posted it and fixed it. However, its still giving me the same errors as posted above.

[Einherjar]

I don't understand what are you guys are trying to do...

You just wanted to shuffle the integers, right?
So why won't this work?

code:

public void shuffle () {                 for (int i = 52; i > 0; i ++) {                         list.add(list.remove((int)(Math.random() * i)));                 }         }

[DemonWasp]

Einherjar @ Wed Nov 26, 2008 1:43 am wrote:

So why won't this work?

code:

public void shuffle () {                 for (int i = 52; i > 0; i ++) {                         list.add(list.remove((int)(Math.random() * i)));                 }         }

For starters, the infinite loop is a poor choice, as is the out-of-range indexing. You probably meant

code:

for ( int i = 0; i < N; ++i ) {   list.add ( list.remove ( (int)(Math.random() * N) ) ); }

Secondly, that provides no guarantee that you'll have the required condition (that no two consecutive integers be found adjacent in the result) - in fact, it's fairly likely that it'll happen with this method.

[Einherjar]

Oh, my apologies, didn't read that part.

[riveryu]

I don't think this problem can be solved by randoming each element one by one. The only way may be to find all solutions that satisfy the "must not follow each other" condition, and randomly picking one from those.