The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Hot answers tagged

36

There is a problem with the distribution of your shuffle. Instead of choosing a random index from anywhere in the array, choose an index from zero to i (inclusive). This should prevent the same card from being shuffled twice* and ensure a more even distribution (think of it as being analagous to taking cards out of a deck at random and stacking them on a new ...


29

In general First and foremost, you were asked to produce a program that generates a list of 10,000 numbers in random orders. You've added far too much complexity. There's no need for input or output (other than the final output). It's not a good immediate impression to heavily over-architect the program. I would be expecting a few lines of code (5-10), with ...


19

The fact that Python allows fitting things on a single line and pack in comprehensions, does not mean you need to try to squash the code to be shorter hurting readability. I would probably at least expand the code into multiple lines with descriptive variable names. Here is, though, an alternative solution based on regular expression replacement function: ...


17

I see some problems with it: You are reinventing the wheel. Use Collections.shuffle(); The code only shuffles an array of 77 elements. What would you do if the array had 2 elements? What would you do if the deck contains more than 77 elements? Your array is a list of Strings. No much reuse. Could not be part of a library. You could at least move the swap to ...


17

I totally agree with @alecxe's comment on Python, but I thing regex is a little overkill for this problem. So, here's a non-regex solution: import random def shuffle_string(string): chars = list(string) random.shuffle(chars) return ''.join(chars) def garble_word(word): # No operation needed on sufficiently small words # (Also, main ...


13

Performance The shuffle implementation is very inefficient, as removing a random item from a list is inefficient. Searching for the element to remove is an \$O(n)\$ operation, and then removing it from the middle of the list is expensive, as the subsequent elements may have to be shifted (when the list is backed by an array). A better algorithm is to ...


12

@Loki Astari is correct in his comment: rand() is well know for its bad distribution. But you are using it correctly. Note: rand() % currentIndexCounter does not give you a perfect distribution unless currentIndexCounter is an exact divisor of RAND_MAX. You may want to look at C++11 random header and the generators provided inside. Since you're using C++...


12

Naming First of, what you have created is not an iterator so naming it as such is misleading. I would recommend a name but I actually think that you should redesign your class and the name I would recommend wouldn't be fit for the redesigned class so I'll wait with that until the end. Design In C++ as opposed to Java, when you assign an object you get a ...


11

First off I want to say that your decision to make an array that represents the ordering permutation is a really good idea. Many people would have passed in the array to be shuffled and had it mutated. Returning a permutation and applying that to an ordered array is a conceptually much nicer way to go. Your shuffle algorithm has an interesting and common ...


11

Docs and comments This is my personal preference but for me a xml comments with no content are not necessary. For example <returns></returns> tells me virtually nothing about returning type or what is being returned etc. As stated in other answer comments like this: // Get the minimum range value. Console.Write("\nPlease enter the minimum ...


11

As this is interview code for discussion, I'll frame my answer as a set of open-ended discussion questions. "How would you incorporate this into a bigger program?" This one's fairly easy - most of your program is in the test harness, and you should be able to extract Randomize() and use it elsewhere. You'll probably want to talk about how you document the ...


10

Algorithm This algorithm is already provided by the standard library. std::random_shuffle() If you want to implement it yourself then this is not very optimal (as @rolfl mentioned this is \$O(N^2)\$ at best). @rolfl suggests using Fisher-Yates I call it the Knuth shuffle but basically it is the same thing (and Knuth is a cooler name to throw around :-) The ...


10

You should create a immutable Card class that hold the value and suit and use an enum for the suit values: public class Card{ public static enum Suit{ HEARTS, CLUBS, SPADES, DIAMONDS; } public final int value; public final Suit suit; public Card(int value, Suit suit){ this.value = value; this.suit = suit; } } ...


10

Naming I would write array out instead of shortening it to arr (it's just two more letters), because it's more readable (but I do like that you are very consistent with your shortening). is there a reason that you are using ii/jj instead of the more commonly used i/j? Spacing You should use a lot more spaces, because they make your code easier to read. ...


10

You can use the inside out version of the Fisher-Yates shuffle In C# it would look like: private static int[] Shuffle(int n) { var random = new Random(); var result = new int[n]; for (var i = 0; i < n; i ++) { var j = random.Next(0, i + 1); if (i != j) { result[i] = result[j]; } ...


10

I see carefully crafted code and attention to detail. I think you're on a good track, keep it up. Program organization It would be better to split the implementation to multiple classes, for example: A class to be the main executable as per the problem description: generate a list of 10,000 numbers in random order. I would make this a console application, ...


9

Your algorithm is guaranteed to have bias. Your program can draw \$77^n\$ different equally likely random sequences, but there are \$n!\$ possible permutations of input. You can think of a sequence of random numbers as a ball, permutations of input as holes, and program as the process of throwing balls into the holes. Fair shuffler should end up with the ...


9

The others have already posted out most points, so I'll briefly recap my opinion on them and provide an easier example: You are using some random object range in int abc = rm.nextInt(77), I suppose you wan to use rm.nextInt(array.length) such that it scales with your input. Please try to use meaningful variable names. int abc and Random rm are utterly ...


9

Reinventing the wheel For the record, you can use Collections.shuffle to shuffle collections. I suppose you're doing this for the sake of the exercise. Ergonomy The implementation is not ergonomic. It's not easy to use. I would expect from a generator to return something that's iterable, so that I can loop over its elements, and stop anytime I want, ...


9

In this review, I'll omit the code that was not implemented by you. At some point, you can try to figure out how it works and then replace it with your own implementation that can be reviewed here. As a beginner, it's great to see that you've started using functions to increase modularity. However, you can use more, as main() is still doing a lot of work. ...


9

Everything is static. This might be fine in this case, but it's bad style in general. And no OOP. You don't really need to create an object for this assignment, but in case you do, you can make more fancy things. For example, store a Random in a field. This way you can choose seeded Random so you want it to always do the same (nice for debugging) unseeded ...


8

Your algorithm is very sub-optimal. Essentially you take a copy of the input array, then you randomly pick an index values, making sure you have not yet picked that index. Once you have randomly selected the indices, you then copy the data back from the temp copy, back to the input array. The bottom line is that you loop through the indices once, and, for ...


8

Readability currentListIndex-1 < 0 I'd make that currentListIndex <= 0 That way you simplify the statement. Shuffling As pointed out in a previous answer on your first question, you can make use of Collections.shuffle (example source if you're interested to see how it works). You can even keep using your Random object. It would look kinda like ...


8

In several places, where you could have (and I think should have) used a simple for statement, for example, for (int index = 1; index < length_of_source; ++index), you instead wrote a do statement that scatters the logic of the loop control and makes the program more difficult to understand. On a different note, do not reseed the rand function (at least ...


7

Comments: about all of your comments add close to no value to your code. //get random number from 0 to new range of unshuffled deck int randomDraw = r.Next(0, initial.Count); Your comment just writes out, what your code does in the next line. This is unneccesary noise and you should not do it. The probably only acceptable comment is this one: for (int i =...


7

I would remove the: if( size > 0 ) and replace the do {...} while with a while {...} to simplify the structure of the code. You can also redesign your algorithm to simplify it further. You can use an Array instead of ArrayList and use the following shuffle algorithm which avoids the use of a supplementary array. Here is the complete code: import ...


7

Object-oriented design There is more data being passed around than should be necessary with an object-oriented design. You have ran (a Random object) and tileGrid (a 2-D matrix) as instance variables. I don't think that there's much point to keeping a Random object as part of the puzzle's state; it would only be useful in .shuffle(), so it could just be a ...


7

There are no docstrings. It's hard to review code when we don't know what it is supposed to do. The various shuffle functions both modify their items argument and return it. It would be clearer if these functions either modified their argument without returning it (like random.shuffle) or returned a new list without modifying the original (like random.sample)...


7

The logic part of your code should definitely be re-written, but since it's one big mess I'm not going to touch that. See whether you really need that many options. You probably don't. I might expand on this anyway later on, since code like this hurts. However, I can tell you this smells: List<string> MaleNamesThatStartWithA; List<string> ...


7

Add space between your functions, PEP8 suggests two spaces, but honestly any amount of space would be better than none. There's not much of a difference between shuffle and shuffle_v2: You've written a for loop as a while loop. Which doesn't make much sense as Pythons for loops are really clean and easy to use. You use different bounds for your random....


Only top voted, non community-wiki answers of a minimum length are eligible