[iDecimate]

Hello, im doing a game project for my grade 12 programming that is similar to dont forget the lyrics, essentially the user is shown lyrics and they need to guess what song it is, the way I display the lyrics is in a for loop that generates a random number from 0-27 and each song lyrics have their own number associated with them, the only problem is that some of them get duplicated, what is the easiest way to prevent this, Ive heard of something called and arraylist but im a little unaware of how this works, just started programming in java so a good explanation of this would be greatly appreciated, Thank you! Paul

[jon.kiparsky]

ArrayList is well documented. Start by reading this. The thing that might be hardest to get hold of at the start is the concept of generics.

An ArrayList isn't just a list that you can throw anything into - well, it can be, but that causes a lot of problems if you do it that way. Instead, you make it an ArrayList of some type:

ArrayList<String> myArrayList = new ArrayList<String>();

This means that myArrayList is an ArrayList of Strings - anything that you put in it has to be a String, and anything you remove from it is guaranteed to be a String. This is useful, because you can take String out of it and know that they are Strings, and not Porcupines or BufferedWriters or whatever.


You can remove objects from an ArrayList by index, and ArrayList has a size() method which tells you how many items it holds at the moment, which means, yes, it's very easy to do this with an ArrayList. You just have to generate a random non-negative integer less than the number of items in the list, and remove the item at that index.

[Ryano121]

Or you could use a HashMap instead which perhaps better handles the links between the numbers and the lyrics -

HashMap<Integer, String) lyrics = new HashMap<Integer, String>(); // create the structure

lyrics.put(1, "some lyric"); // add a lyric. The 'key' of 1 is associated with the String "some lyric"
lyrics.put(2, "some other lyric"); // add a lyric. The 'key' of 2 is associated with the new String "some other lyric"

String lyric = lyrics.get(1); // get the lyric associated with the number 1
// Here the value of lyric will be "some lyric"

Similarly the HashMap has a .remove method similar to ArrayList, yet accepts a 'key' instead. So -

lyrics.remove(2);
// Will remove "some other lyric" from the hashmap

Some more reading

It should however be said that it's probably easier to use an ArrayList and just have the numbers as indexes rather than fill the HashMap with sequential numbers. Although it's always good to read up on both data structures anyway.

Good luck.

This post has been edited by Ryano121: 24 May 2012 - 01:28 PM

[iDecimate]

Thank you for the replies! I'll try to see if I can get it done, dont have code with me atm just wanted to see how it would get done, ill finish it up tomorrow at school, thanks again for the assistance

[hws]

you can create random numbers by using random class which is Random random = new Random(); then if you want from 0 to 27 you can do a for loop and inside it put int n =0 + random.nextInt(28);//as an example and to avoid duplicates you can use classes like arrayList or linkedList and if(!arrayList.contains(n)){then add} for example//the contains check if there is a value like it so using it with! check if it doesn't contain that value and if it don't then it will add it that's a good way to avoid duplicates.

[g00se]

See http://technojeeves....-random-numbers

[cfoley]

Another option is shuffling an array of numbers like in the code below.

A cookie to whoever can tell me why my shuffle algorithm is unfair. (also the same reason why all the algorithms explained above are unfair too).

import java.util.*;

class Main {
	
	public static void main (String args[]) {
		int[] arr = make(27);
		shuffle(arr);
		System.out.println(Arrays.toString(arr));
		
	}
	
	static int[] make(int max) {
		int[] result = new int[max + 1];
		for(int i = 0; i < result.length; i++) {
			result[i] = i;
		}
		return result;
	}
	
	static void shuffle(int[] arr) {
		Random rand = new Random();
		for (int i = 0; i < arr.length; i++) {
			int index = rand.nextInt(arr.length - i) + i;
			int temp   = arr[i];
			arr[i]     = arr[index];
			arr[index] = temp;
		}
	}
	
}

This post has been edited by cfoley: 26 May 2012 - 04:47 PM

[pbl]

int index = rand.nextInt(arr.length - i);

Is not really fair. You switch each elemnt of the array with a randomly selected number from a set that comes smaller and smaller.

Will be a lot better that way (even if you might shuffle an element with itself)

	static void shuffle(int[] arr) {
		Random rand = new Random();
		for (int i = 0; i < arr.length; i++) {
			int index1 = rand.nextInt(arr.length);
			int index2 = rand.nextInt(arr.length);
			arr[index1] ^= arr[index2];
			arr[index2] ^= arr[index1];
			arr[index1] ^= arr[index2];
		}
	}	

But still prefer that one
http://www.dreaminco...snippet2992.htm

This post has been edited by pbl: 24 May 2012 - 06:15 PM

[cfoley]

My algorithm is really the same as the one you linked to. I start with a list of numbers and an empty list. One by one, I choose a number at random from the first list and append it to the second. Since one list is growing and the other is shrinking, I can get away with putting them at different ends of the same array.

The swapping algorithm you posted in this thread, even if the random function was fair, will bias the numbers slightly to remain in their original positions. Increasing the number of iterations would reduce this problem.

My algorithm not being fair IS to do with the random function not being truly random but there was a specific detail I was looking for.

[pbl]

cfoley, on 25 May 2012 - 03:57 AM, said:

I start with a list of numbers and an empty list. One by one, I choose a number at random from the first list and append it to the second.

It is the code you posted that is supposed to do that ?
It is passing through all elements of the list and swtching it with another, randomly selected, element of the list. The last element is always swicthed with element[0]

[Sheph]

See http://www.cigital.c...er_gambling.php for a good explanation on bad shuffling algorithms. It gives a nice tree of all the possibilities for 3 cards. cfoley is right, though. His algorithm will produce each possibility with equal probability, while producing two random numbers will not. I believe we had this discussion already though: http://www.dreaminco...y-from-an-file/

Edit: my mistake, his algorithm is off I because he's not adding i to his random number to offset the range. His i gets bigger as his range gets smaller 0-(size-i) he should add i so the numbers he already swapped are not chosen again.

This post has been edited by Sheph: 25 May 2012 - 04:18 AM

[cfoley]

Nice catch Sheph. I've amended the code. Apologies to pbl if that bug is why you disagreed with me.

The answer I was looking for is that random number generators depend on a seed. Any time you create a new Random object with the same seed you will get the same sequence of numbers. This is useful for testing and debugging since you can get repeatable runs of numbers.

Seeds are long which gives a huge range of numbers. However, the number of permutations of 27 objects dwarfs the number of longs. It's of the order 10^28 which is crazy. Even if every seed gave a unique shuffling you would still only be able to generate a fraction of the possible permutations. It's because some permutations are more likely than others that makes all our algorithms unfair.

[pbl]

cfoley, on 26 May 2012 - 08:00 PM, said:

The answer I was looking for is that random number generators depend on a seed. Any time you create a new Random object with the same seed you will get the same sequence of numbers.

And where do you see in the previously posted code 2 Random numbers generators generated with the same seed ?

[pbl]

cfoley, on 26 May 2012 - 08:00 PM, said:

The answer I was looking for is that random number generators depend on a seed. Any time you create a new Random object with the same seed you will get the same sequence of numbers. This is useful for testing and debugging since you can get repeatable runs of numbers.

This is true in C/C++ which have ran() init with the same seed but noyt in Java my friend

So:
- in C when running benchmarks, no need to initialize ran() it will always return the same random numners
- in Java, if you want to return always the same numbers at each program run, you have to int Random() with always the same number

    /**
     * Creates a new random number generator. This constructor sets
     * the seed of the random number generator to a value very likely
     * to be distinct from any other invocation of this constructor.
     */
    public Random() { this(++seedUniquifier + System.nanoTime()); }
    private static volatile long seedUniquifier = 8682522807148012L;

    /**
     * Creates a new random number generator using a single {@code long} seed.
     * The seed is the initial value of the internal state of the pseudorandom
     * number generator which is maintained by method {@link #next}.
     *
     * <p>The invocation {@code new Random(seed)} is equivalent to:
     *  <pre> {@code
     * Random rnd = new Random();
     * rnd.setSeed(seed);}</pre>
     *
     * @param seed the initial seed
     * @see   #setSeed(long)
     */
    public Random(long seed) {
        this.seed = new AtomicLong(0L);
        setSeed(seed);
    }

And YES your algorithm is still wrong, compared to mine, despite everything Java tried to help you not to screw it up

This post has been edited by pbl: 26 May 2012 - 09:21 PM

[jon.kiparsky]

All of this footling about, and I still say that for the original poster's question, removing random elements from the arraylist is the way to go. Why shuffle the array at all?
And if you want to suffle an arraylist, just use the same technique: pull randomly from alist1 and add to alist2. Assuming your random numbers are sufficiently random, this gives each element of alist1 an equal chance to be in any position of alist2, which is to say it shuffles correctly. The process is easy to understand, so the next guy to touch it won't screw it up. And it's efficient: for each element, it does one call to random and one move.
And because you know how many elements you're shuffling, you don't even have to worry about losing time expanding alist2, since it can be created with the correct capacity.

Sometimes I think you smart kids are a little too smart for your own good...