• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Jeanne Boyarsky
  • Devaka Cooray
  • Paul Clapham
Sheriffs:
  • Tim Cooke
  • Knute Snortum
  • Bear Bibeault
Saloon Keepers:
  • Ron McLeod
  • Tim Moores
  • Stephan van Hulst
  • Piet Souris
  • Ganesh Patekar
Bartenders:
  • Frits Walraven
  • Carey Brown
  • Tim Holloway

Collections.shuffle without repeat

 
Greenhorn
Posts: 9
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, I created Array which show Random items. But unfortunately sometimes items from Array are repeated. How can i create Collections without repeat ? Thanks in advance



 
Rancher
Posts: 4116
47
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
All those Quote instances are unique, so you won't get repeats from a shuffle of the array.

By the way, the last two should be attributed to Pilsudski, at a guess, and not Einstein.
 
Bart Ret
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Dave Tolls wrote:All those Quote instances are unique, so you won't get repeats from a shuffle of the array.

By the way, the last two should be attributed to Pilsudski, at a guess, and not Einstein.



Thanks for your reply. What can i do in this situation?... BTW Yeah you are right It should be Pilsudzki.
 
Marshal
Posts: 6851
470
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Bart Ret wrote:What can i do in this situation?


In which?
 
Bart Ret
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Liutauras Vilda wrote:

Bart Ret wrote:What can i do in this situation?


In which?


To find solution in non repeating Array items
 
Dave Tolls
Rancher
Posts: 4116
47
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
But you haven't got any repeating array items.
 
Liutauras Vilda
Marshal
Posts: 6851
470
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
@OP

With repeating items - with duplicates
Without repeating items - all items unique

As Dave mentioned, you have all items unique.

Is by any chance you are asking what to do if you have duplicate items? (In which case you were asking an opposite thing).
 
Bart Ret
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Dave Tolls wrote:But you haven't got any repeating array items.



175/5000
I didn't specify my problem more. I have a button assigned to the ShuffleQuote () method, which  draws one random Array Item. Problem is in situation that  sometimes the randomly drawn elements are repeated. I would like to avoid it.
Below is rest of my code:

 
Dave Tolls
Rancher
Posts: 4116
47
  • Likes 2
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Then only shuffle once, picking th next item in the List each time they click the button.

Of course you then need to decide what to do when you get to the end of the List.
 
Bart Ret
Greenhorn
Posts: 9
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator

Dave Tolls wrote:Then only shuffle once, picking th next item in the List each time they click the button.

Of course you then need to decide what to do when you get to the end of the List.



Thanks, I'll try this
 
Liutauras Vilda
Marshal
Posts: 6851
470
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Instead of shuffling, you could also try to pick quote "randomly", so the idea would differ in the sense of:

currently:
  • croupier shuffling cards, then asking player1: pick top card
  • croupier shuffling cards, then telling to player2: let me shuffle again, this card already been picked
  • croupier shuffling cards, then telling to player2: let me shuffle again, this card already been picked
  • ...


  • you could:
  • croupier to player1: pick any random card from the deck and keep it
  • croupier to player2: pick any random card from the deck and keep it...


  • you also could:
  • croupier shuffling cards, then asking player1: pick top card and keep it
  • croupier shuffling cards, then asking player2: pick top card and keep it...

  •  
    Bart Ret
    Greenhorn
    Posts: 9
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Liutauras Vilda wrote:Instead of shuffling, you could also try to pick quote "randomly", so the idea would differ in the sense of:

    currently:

  • croupier shuffling cards, then asking player1: pick top card
  • croupier shuffling cards, then telling to player2: let me shuffle again, this card already been picked
  • croupier shuffling cards, then telling to player2: let me shuffle again, this card already been picked
  • ...


  • you could:
  • croupier to player1: pick any random card from the deck and keep it
  • croupier to player2: pick any random card from the deck and keep it...


  • you also could:
  • croupier shuffling cards, then asking player1: pick top card and keep it
  • croupier shuffling cards, then asking player2: pick top card and keep it...



  • Thank you for your answer. Yes is good idea but i've got many array items (not only 10)
     
    Sheriff
    Posts: 13510
    223
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Don't conflate randomness with uniqueness - a random sequence does not preclude duplicates.  In other words, you cannot assume elements of a random sequence will not (eventually) be repeated.

    I like Dave's suggestion of shuffling to mix up the order then just sequentially give out the elements of the shuffled list.

    This may have already been suggested but alternatively, you can pick out a random element from 0 to n-1 where n is the total number of elements then swap the chosen element with the n-1 element. On the subsequent round, you randomly pick from elements 0 to n-2 and swap that one with the n-2 element. Then pick from 0 to n-3 and swap with the n-3 element, and so on until you have exhausted the entire list.
     
    Bart Ret
    Greenhorn
    Posts: 9
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Junilu Lacar wrote:Don't conflate randomness with uniqueness - a random sequence does not preclude duplicates.  In other words, you cannot assume elements of a random sequence will not (eventually) be repeated.

    I like Dave's suggestion of shuffling to mix up the order then just sequentially give out the elements of the shuffled list.

    This may have already been suggested but alternatively, you can pick out a random element from 0 to n-1 where n is the total number of elements then swap the chosen element with the n-1 element. On the subsequent round, you randomly pick from elements 0 to n-2 and swap that one with the n-2 element. Then pick from 0 to n-3 and swap with the n-3 element, and so on until you have exhausted the entire list.



    Thank you for your reply:). Could you show me example code of your solution?(I can't understand this a little bit)
     
    Bartender
    Posts: 2291
    95
    Google Web Toolkit Eclipse IDE Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    I have a slightly different idea ...
    Just simply create a list of items, shuffle it and pop it's 0th item to get a fresh random item every time. If the new list is empty, you no longer have items to get.
    A very simple component can be like:
     
    Ranch Foreman
    Posts: 3266
    19
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Here's one I've posted previously:

    It produces a shuffled sequence of integers from 0 to n-1. For your app, these can be used as indices for quotesArray.  This algorithm is pretty close to what Junilu describes, although it picks from the back part of the array rather than the front.  So while Junilu's second pick is chosen from 0 to n-2 inclusive, mine is from 1 to n-1.  And Junilu's third pick would be chosen from 0 to n-3, while mine would be from 2 to n-1.  But it's the same idea.  

    This algorithm is extremely lazy - it only shuffles as many elements as you actually need.  If you have a list of 10000 elements and you need 10 of them,  Collections.shuffle() would shuffle all 10000 elements, then you look at the first 10.  While with mine, you call next() 10 times, and each time it randomly picks exactly one more element.  So Collections.shuffle() will call Random.nextInt() 10000 times, while I will call it just 10 times.
     
    Mike Simmons
    Ranch Foreman
    Posts: 3266
    19
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    @salvin, I would recommend against using randomList.remove(0) on an ArrayList.  That's an O(N) operation each time you call it.  I would either remove from the end, or use a LinkedList.  Either would be O(1).
     
    salvin francis
    Bartender
    Posts: 2291
    95
    Google Web Toolkit Eclipse IDE Java
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Mike Simmons wrote:@salvin, I would recommend against using randomList.remove(0) on an ArrayList.  That's an O(N) operation each time you call it.  I would either remove from the end, or use a LinkedList.  Either would be O(1).


    Agreed, Another idea stuck my mind.. I need not duplicate the entire list, all I need is the indexes in the shuffled order. How does that sound ?
     
    Mike Simmons
    Ranch Foreman
    Posts: 3266
    19
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Agreed.  That's why my next() just returns an int.
     
    Marshal
    Posts: 24594
    55
    Eclipse IDE Firefox Browser MySQL Database
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Dave Tolls wrote:By the way, the last two should be attributed to Pilsudski, at a guess, and not Einstein.



    The internet is full of quotes which weren't actually said by Einstein.
     
    Junilu Lacar
    Sheriff
    Posts: 13510
    223
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Likes 3
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    "The internet is full of quotes which weren't actually said by Einstein." —Abraham Lincoln

     
    Dave Tolls
    Rancher
    Posts: 4116
    47
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Paul Clapham wrote:
    The internet is full of quotes which weren't actually said by Einstein.



    true, but I'm pretty sure I've never seen:
    "To be defeated and not submit, is victory; to be victorious and rest on one's laurels, is defeat."
    attributed to Einstein...
     
    Bart Ret
    Greenhorn
    Posts: 9
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Hello again everyone:)

    I just started doing it today, and i came up with something like that. But unfortunetly i ve got error:

    at com.example.cytatnadzi.MainActivity.ShowRandomQuote(MainActivity.java:70)
    at com.example.cytatnadzi.MainActivity.onCreate(MainActivity.java:45)




     
    Mike Simmons
    Ranch Foreman
    Posts: 3266
    19
    • Likes 1
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator
    Arrays.asList(array) returns a List that does not support removal.  If you want to do it this way, I'd replace the array with a LinkedList that's initially populated from the array - e.g. new LinkedList<>(Arrays.asList(quotesArray)).  The new LinkedList starts as a copy of the one from Arrays.asList(), but as you remove elements from the LinkedList, they are still in the array and in the list from Arrays.asList().

    By the way, do you know what you want to do when the list is eventually empty?  Will you start over with a new list copied from the original array?
     
    Bart Ret
    Greenhorn
    Posts: 9
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Mike Simmons wrote:Arrays.asList(array) returns a List that does not support removal.  If you want to do it this way, I'd replace the array with a LinkedList that's initially populated from the array - e.g. new LinkedList<>(Arrays.asList(quotesArray)).  The new LinkedList starts as a copy of the one from Arrays.asList(), but as you remove elements from the LinkedList, they are still in the array and in the list from Arrays.asList().

    By the way, do you know what you want to do when the list is eventually empty?  Will you start over with a new list copied from the original array?




    to be honest, i don't know
    Do you think about something like that?
    BTW. Like you said , it doesn't work properly. Still are repeated items.
     
    Paul Clapham
    Marshal
    Posts: 24594
    55
    Eclipse IDE Firefox Browser MySQL Database
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Bart Ret wrote:BTW. Like you said , it doesn't work properly. Still are repeated items.



    Yes. Your code shuffles the items, then picks one and displays it. Then it shuffles the items, then picks one and displays it.

    I haven't been watching this thread for a while and now there's 24 posts, but it seems to me that the idea of "shuffle the items, then display them one at a time until they are all used up" must have been discussed at some point.

    Mike Simmons wrote:By the way, do you know what you want to do when the list is eventually empty?  Will you start over with a new list copied from the original array?



    You wrote:to be honest, i don't know
    Do you think about something like that?



    Well, if you don't want repeated items then you won't want the last item in one group to be the same as the first item in the next group, right?
     
    Mike Simmons
    Ranch Foreman
    Posts: 3266
    19
    • Mark post as helpful
    • send pies
    • Quote
    • Report post to moderator

    Bart Ret wrote:BTW. Like you said , it doesn't work properly. Still are repeated items.


    OK, you've got a LinkedList as I suggested - but it's only held in a local variable, quotesList.  Each time you reach the end of this method, that variable goes out of scope, and that particular LinkedList will never be accessed by another method call in the future, because no one has a reference to it.  The only reference ended when the method ended.  Instead, the next time the method is called, it makes a new LinkedList whose alues are populated from quotesArrays, the original array which has never changed.  Try making quotesList a field of your class, not a local variable.  Then the next call to ShowRandomQuote() will have a way to get a reference to the same list that you previously removed one or more elements from.
     
    Consider Paul's rocket mass heater.
    • Post Reply Bookmark Topic Watch Topic
    • New Topic
    Boost this thread!