Random accessing array, how to skip duplicates?

Question

I have an XML array that I access to pull a random question from. How would I go about making sure there is no duplicates pulled? My current code follows.

    private void getQuestion() {
    // TODO Auto-generated method stub

    res = getResources();
    qString = res.getStringArray(R.array.questions);

    rQuestion = qString[rgenerator.nextInt(qString.length)];

    tokens = new StringTokenizer(rQuestion, ":");
    wordCount = tokens.countTokens();
    sep = new String[wordCount];
    wArray = 0;
    while (tokens.hasMoreTokens()) {
        sep[wArray] = tokens.nextToken();
        wArray++;
    }

}

Any help would be appreciated.

score 5 · Answer 1 · answered Dec 18 '11 at 02:03

5

The Fisher-Yates shuffle is an algorithm that is more or less designed for this purpose.

answered Dec 18 '11 at 02:03

Oliver Charlesworth

267,707
33
569
680

I've added an answer using ArrayList and Collections.shuffle() which you might be interested in. – Maarten Bodewes Jan 05 '12 at 23:00

score 0 · Answer 2 · edited May 23 '17 at 12:03

You are better off putting that array of questions in a list and use Collections.shuffle(). After that, simply iterate through the list. More information can be found at this related answer.

This solution will cost some memory for duplicating the list, but remember that the strings themselves won't be copied, only the references to the questions are. For maximum performance, use a list with random access (ArrayList), or use that as a replacement for the array. If you don't theshuffle method will create one internally.

score -1 · Answer 3 · answered Dec 18 '11 at 02:08

-1

If you want a fast way of getting only unique values from an array this link has a very fast method. Below uses an ArrayList, but it will not be hard for you to convert from string array to an ArrayList - or just use ArrayLists instead.

e.g. new ArrayList(Arrays.asList(myArray));

In short you use a hashset to only get unique values using this method

public static ArrayList GetUniqueValues(Collection values)
{
    return new ArrayList(new HashSet(values));
}

Then use it like so

ArrayList x = new ArrayList();
x.add("abc");
x.add("abc");
x.add("abc");
x.add("def");
x.add("def");
x.add("ghi");

for (Object y : GetUniqueValues(x))
    Log.d("something", y); //ok lets print the value

To yield the result of "abc, def, and ghi"

To be clear I agree with Travis to ask why you have duplicates. The above is to answer the question.

answered Dec 18 '11 at 02:08

Graham Smith

25,627
10
46
69

The main problem with this solution is that it will sort your values. For example, the list will be composed of `abc, def, ghi` no matter what order they were added in. This shouldn't be a problem in this case, but it's something to keep in mind. – Alexis King Dec 18 '11 at 02:14
I do not have duplicates, but the method i posted can and does return the same answer multiple times, as in the random was the same, so the same string in the same position in the array was pulled twice – Bill Gary Dec 18 '11 at 03:50
Sorry I was not of much help. I would look at the other answer by Leo that is probably the way I would handle your scenario. My thanks to Jake for contributing more to my answer. – Graham Smith Dec 18 '11 at 19:29

score -1 · Accepted Answer · answered Dec 20 '11 at 04:35

I figured it out. I switched it to

private void getQuestion() {
    res = getResources();
    qString = res.getStringArray(R.array.questions);
    arrayLength = qString.length;
    qTotal = arrayLength;

}

private void getRandom() {
    rnd = rgenerator.nextInt(arrayLength);
    rQuestion = qString[rnd];
    qString[rnd] = "used";
    seperate();

}

private void seperate() {
    if (rQuestion != "used") {
        tokens = new StringTokenizer(rQuestion, ":");
        wordCount = tokens.countTokens();
        sep = new String[wordCount];
        wArray = 0;
        while (tokens.hasMoreTokens()) {
            sep[wArray] = tokens.nextToken();
            wArray++;
        }
        qNumber++;
    } else {
        if (qNumber < qTotal) {
            getRandom();
        } else {
            startActivity(new Intent("com.example.END"));
        }
    }

}

It gets the array from resources, then pulls a random question from the array. It then sets that one to "used" and splits it. It also checks to see if the pulled question is "used, and if it is, it pulls another question. It also goes to the end game activity if all questions are "used"

If you have enough questions, you might be surprised how long you will have to wait for that algorithm to find the last question, and the maximum waiting time (the order) is even infinite. — Maarten Bodewes, Jan 05 '12 at 22:44

Random accessing array, how to skip duplicates?

4 Answers4