• 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 Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Ron McLeod
  • Paul Clapham
  • Jeanne Boyarsky
  • Liutauras Vilda
Sheriffs:
  • Rob Spoor
  • Bear Bibeault
  • Tim Cooke
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Piet Souris
Bartenders:
  • Frits Walraven
  • Himai Minh

Shuffling the characters of a string. (Learning about lists)

 
Ranch Hand
Posts: 48
Eclipse IDE MySQL Database Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The following code works, however, I feel like there must be a better way to do it.
My questions are:  1. Is there a more elegant way to do the shuffle while still using a list, 2. How would I change the code if I wanted to return the list (as a list, not a string), and 3. Is there a more elegant way to do this shuffle using any means.


As always, thank you for your time and consideration!
~d
 
Marshal
Posts: 72913
330
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
There are all sorts of studies about randomisation and shuffling. It has come up here before; let's see if I can't find it (the English grammar proves I have lived in London). Look at my two posts in the following link: this one has two links to older posts and a reference to Bloch and Gafter in. Yes, Collections#shuffle() is the most elegant way to shuffle a List. Consider different ways to create the List;-Putting Integers back to a String is slightly more awkward; you have to turn the ints to chars or their boxed equivalent No you don't; you simply have to remember which methods are available:-Line 4 is redundant or optional and may be omitted.
 
Marshal
Posts: 7982
560
Mac OS X VI Editor BSD Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

David Cone wrote:


That's nice. Welcome to the Ranch Well, you have a few posts already.

Two comments from me, which are not related exactly to your question.

1. Class names supposed to start with an Upper case. So that would be ListPlayer.

2. shuffleStringAsList() I know you are just playing with some code, hence such class name, but in other situations, try not to reveal method internal mechanics how the shuffling is done. So the method name shuffleString() should work just well. Why not to reveal internal mechanics? Because the user of your method doesn't need to know that, all he cares that string would get shuffled. Also, you may decide to change the mechanics after 10 years if there would be a better way, i.e. shuffleStringAsCampbellSuggested(), so you won't go and change method name every single time you learn a better way.
 
David Cone
Ranch Hand
Posts: 48
Eclipse IDE MySQL Database Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@Liutauras Vilda

Liutauras Vilda wrote:1. Class names supposed to start with an Upper case. So that would be ListPlayer.



I did it again before I got to read your post.   What is the easiest way to fix that in Eclipse IDE?  Create a new "java project" with the correct case and cut and past the code, then correct the case in the code? I'll try that now.

I was just on my way trying to fix this when Eclipse IDE complained about Uppercase as the first Character of the Package....  Package should be Lowercase, Class Uppercase?



Liutauras Vilda wrote:2. shuffleStringAsList() I know you are just playing with some code, hence such class name, but in other situations, try not to reveal method internal mechanics how the shuffling is done. So the method name shuffleString() should work just well. Why not to reveal internal mechanics? Because the user of your method doesn't need to know that, all he cares that string would get shuffled. Also, you may decide to change the mechanics after 10 years if there would be a better way, i.e. shuffleStringAsCampbellSuggested(), so you won't go and change method name every single time you learn a better way.



As I learn new ways of doing it I create a new method under the original with new descriptive name...  Would never do it outside my own sandbox.  Thank you for the reminder.  So I don't develop a bad habit, I'll start doing it the right way and put any internal info in comments.  I created two new methods in the below code and include what I return in the name...  Is that OK, or is that bad too?  Should I use sStringShuffleS and sStringShuffleL or something else?


@Campbell Richie

WooHoo!  I figured out the list method with a little help (ok, a lot of help) from DuckDuckGo.  I'm feeling joyously geeky right now!  :-)



If I could jump up and tap my heals, I would!
~d

 
Campbell Ritchie
Marshal
Posts: 72913
330
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Damn! I spent ages writing replies and they all disappeared.

David Cone wrote:. . . What is the easiest way to fix that in Eclipse IDE?  Create a new "java project" with the correct case and cut and past the code, then correct the case in the code? . . .

No. Change the name and then Eclipse has a refactoring tool that will correct the name wherever necessary.

. . .  Package should be Lowercase, Class Uppercase?

Usually, yes. But package names have some strange conventions: see Java™ Tutorials.

. . . shuffleStringAsCampbellSuggested(), . . .

Only if you think my suggestion is indeed better.  

. . . So I don't develop a bad habit

Quite right.

. . . any internal info in comments.

Good idea to acknowledge help and record its location in case you need to look for it again.
I myself prefer to reserve // comments for something short and use /* comments */ for anything longer. I might also move those comments inside the methods.

. . . Should I use sStringShuffleS and sStringShuffleL or something else? . . .

Afraid I don't like either name. They are difficult to read aloud, for a start. The method in line 38 does two things, creating a List and later shuffling it. The ideal is for a method to do one thing only, so it should be divided into two methods. This is where things start to go wrong. What should you call them?
  • 1: toCodePointList(String)?
  • 2: <E> List<E> shuffled(List<E>)?
  • 2½: void shuffled(List<E>)?
  • Those awkward‑sounding names and signatures made me realise that we are straying from the straight and narrow, the pure path of object‑orientation (=OO). An OO solution might have a field representing the original text, one for the randomised text, and one for the code points List. Or it might have different fields; make them private, and nobody from outside will know anything about them. Maybe your methods (over and above those inherited from Object) should now be called:-
  • 1: getOriginalText()
  • 2: shuffleText()
  • 3: getShuffledText()
  • I hope those suggestions will allow you to create a class following OO conventions.

    Careful about searching; you might not know whether you are going to find something good or bad. You didn't get anything bad there, but didn't anybody mention this method? Nor printf()? You will find all the gory details under Formatter, but what about this?Anyway, you seem to be making progress, and that is what counts
     
    Sheriff
    Posts: 16201
    270
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Here's my first (successful) cut after a quick refactoring:

    or better/clearer yet:
     
    Campbell Ritchie
    Marshal
    Posts: 72913
    330
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    I knocked that code out in about ten minutes, so you can probably improve it no end.
     
    Marshal
    Posts: 3557
    505
    Android Eclipse IDE TypeScript Redhat MicroProfile Quarkus Java Linux
    • Likes 1
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Shuffling using an IntStream of random index values ...
     
    Junilu Lacar
    Sheriff
    Posts: 16201
    270
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Ron McLeod wrote:Shuffling using an IntStream of random index values ...


    Nice...
     
    Master Rancher
    Posts: 3889
    50
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:
    Line 4 is redundant or optional and may be omitted.


    Also, you can leave it out entirely - it's not needed. ;)
     
    Junilu Lacar
    Sheriff
    Posts: 16201
    270
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    David Cone wrote:So I don't develop a bad habit, I'll start doing it the right way and put any internal info in comments.


    Just so you know, many shops consider comments to be code smells. Add comments to explain to the reader why you did something, not how or what the code is doing. As much as possible, you should write code that's expressive enough to not need comments to explain what or how things are being done.
     
    Junilu Lacar
    Sheriff
    Posts: 16201
    270
    Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Take Ron's code, for example. It requires some familiarity with streams and operations on streams but to anyone who is familiar with them already, it's very easy to understand what's going on. Essentially, that code is saying:

    For each distinct index in String s, pick a character in s at a random index and concatenate all of them into a String. There's a beauty and elegance to how that's expressed in the code, if you know how to read it.

    On the other hand, the way I wrote my algorithm is also just as comprehensible: Turn the characters in String s into a list, shuffle that list, then return the list of shuffled characters as a String.

    Neither of these versions of the solution need comments—the code more or less explains itself.
     
    Mike Simmons
    Master Rancher
    Posts: 3889
    50
    • Likes 2
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Ron McLeod wrote:Shuffling using an IntStream of random index values ...


    This is pretty cool.  But one thing I don't like is, it hides some significant inefficiency.    To get 1000 distinct indices, it keeps looking at new random numbers until it finds 1000 distinct values.  That's easy enough at first... but it gets less and less efficient as you go, because you keep generating random numbers that have already appeared, so you try again.  By the time you're try to fill the last distinct value, each attempt has a 1/1000 chance of succeeding.  Here's some code to demonstrate:

    In comparison, when Collections.shuffle() shuffles 1000 elements, it generates exactly 999 random numbers - just what it needs.
     
    Ron McLeod
    Marshal
    Posts: 3557
    505
    Android Eclipse IDE TypeScript Redhat MicroProfile Quarkus Java Linux
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Agreed - it doesn't scale well.  

    I suggested it as a fun alternative, but with smaller strings, it may perform better than other solutions using Collections#shuffle (if that actually matters)??
     
    Campbell Ritchie
    Marshal
    Posts: 72913
    330
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Mike Simmons wrote:. . . Also, you can leave it out entirely - it's not needed. ;)

    No, you would have to delete that line.

    I am not convinced about using a stream. If you use the whole gamut of indices to piuck values for shuffling, you get an enhanced probability of replacing the elements at the beginning of the List. The shuffle method “randomly” chooses indices in the part of the List not already shuffled to get a more even shuffling.
     
    Mike Simmons
    Master Rancher
    Posts: 3889
    50
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Campbell Ritchie wrote:

    Mike Simmons wrote:. . . Also, you can leave it out entirely - it's not needed. ;)

    No, you would have to delete that line.


    Sorry, I thought we were trying to see how many ways we could restate "it's redundant".  

    Campbell Ritchie wrote:I am not convinced about using a stream. If you use the whole gamut of indices to piuck values for shuffling, you get an enhanced probability of replacing the elements at the beginning of the List. The shuffle method “randomly” chooses indices in the part of the List not already shuffled to get a more even shuffling.


    I'm not sure which stream solution you're talking about now.  There's streaming involved in many above solutions... so far, I don't see one that has the bug you describe.  I've also seen that bug (or one that sounds like that) in non-streaming shuffle code in the past.  (Not using Collections.shuffle, but rolling their own.). There's nothing about streams that is more or less conducive to that bug.
     
    Saloon Keeper
    Posts: 4497
    166
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    What about a bit nostalgia? When pc's were introduced at the office, someone showed me a shuffle method: take an element, swap it with the element at the end, take an element from the first n-1 elements, and so on. That was really beautiful, and here's the chance to implement it with Streams:
     
    Campbell Ritchie
    Marshal
    Posts: 72913
    330
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Sorry, I posted in too mudh of a hurry.

    It isn't the streaming that is the problem, as you said. It is that the random numbers are evenly distributed rather than being chosen from the remainder of the List's indices that is the problem. Both Collections#shuffle and I believe Piet's solution correct that problem. I think Ron's solution, now I have seen it, isn' relly shufflng but random selection and it won't have that problem either. It might however take a long time to find the last number, as you pointed out.
     
    Mike Simmons
    Master Rancher
    Posts: 3889
    50
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Piet: yeah, that's roughly what Collections.shuffle is doing:

    (simplified a little)
     
    Campbell Ritchie
    Marshal
    Posts: 72913
    330
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator
    Different from shuffle(), but let's see if we can't implement a random selection from a declining population app. Let's start by creating a population:-Line 1 assumes the length and the code point count will be the same, which means all code points are in the basic plane and will fit in the range of a char.
    See the collect() method about line 4.
    Line 2 should be omitted, deleted, left out, commented out, or not written in the first place if the text is shorter than five (decimal) figures. One page of A4 closely spaced with 12 point type is about 4000 characters.I could envisage running the following code as a Stream, but there is something peculiar about removing elements from the List; it looks like altering my source of data. I shall therefore use a loop:-Both IntStream#range() and Random#nextInt() supply exactly the right results to match the range of indices.You can probably compress that code into a single statement if you don't mind illegible code It says here that remove() runs in linear time, so just like the use of distinct(), this technique will run in quadratic time, but I expect the remove() method will be faster. I am pretty sure that an application with shuffle() will run in linear time.
     
    Liutauras Vilda
    Marshal
    Posts: 7982
    560
    Mac OS X VI Editor BSD Linux
    • Mark post as helpful
    • send pies
      Number of slices to send:
      Optional 'thank-you' note:
    • Quote
    • Report post to moderator

    Mike Simmons wrote:

    Ron McLeod wrote:Shuffling using an IntStream of random index values ...


    This is pretty cool.  But one thing I don't like is, it hides some significant inefficiency.    To get 1000 distinct indices, it keeps looking at new random numbers until it finds 1000 distinct values.  That's easy enough at first... but it gets less and less efficient as you go, because you keep generating random numbers that have already appeared, so you try again.  By the time you're try to fill the last distinct value, each attempt has a 1/1000 chance of succeeding.  Here's some code to demonstrate:

    In comparison, when Collections.shuffle() shuffles 1000 elements, it generates exactly 999 random numbers - just what it needs.


    @OP

    I feel it is worth re-iterating this. Did you understand this post well and what defficiency it was refering to?

    Imagine you were asked to implement a MinesSweeper game, and for the game's state initialization you need to initialize a board N over the M grid with X bombs randomly distributed. Do you see how you could fall into such trap with such kind of problem? For instance if there were a grid 10 x 10 and there were 99 bombs... - that is definitely a lesson to learn from.

    No doubt Ron was aware of that, but if any of you did not get that, raise the hand and we'd re-iterate the issue.
     
    With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
    reply
      Bookmark Topic Watch Topic
    • New Topic