1

I am using the Knuth-Fisher-Yates algorithm to display a shuffled array of string items on a windows form. I do not get any duplicates, which is what I was trying to achieve, however, it only spits out 12 of the 13 elements of the array. How can I get it to display all 13 elements of the array? Here is my code:

private void FormBlue1_Load(object sender, EventArgs e)
{
// set the forms borderstyle
this.FormBorderStyle = FormBorderStyle.Fixed3D;

// create array of stationOneParts to display on form
string[] stationOneParts = new string[13];
stationOneParts[0] = "20-packing";
stationOneParts[1] = "5269-stempad";
stationOneParts[2] = "5112-freeze plug";
stationOneParts[3] = "2644-o'ring";
stationOneParts[4] = "5347-stem";
stationOneParts[5] = "4350-top packing";
stationOneParts[6] = "5084-3n1 body";
stationOneParts[7] = "4472-packing washer";
stationOneParts[8] = "3744-vr valve o'ring";
stationOneParts[9] = "2061-packing spring";
stationOneParts[10] = "2037-packing nut";
stationOneParts[11] = "2015-latch ring";
stationOneParts[12] = "stem assembly";

Random parts = new Random();

// loop through stationOneParts using a Swap method to shuffle
labelBlueOne.Text = "\n";
for (int i = stationOneParts.Length - 1; i > 0; i--)
{
int j = parts.Next(i + 1);
Swap(ref stationOneParts[i], ref stationOneParts[j]);

// display in a random order
labelBlueOne.Text += stationOneParts[i] + "\n";
}
}

private void Swap(ref string firstElement, ref string secondElement)
{
string temp = firstElement;
firstElement = secondElement;
secondElement = temp;
}
Improve this question

5 Answers 5

Reset to default
2

You don't access the first element. for (int i = stationOneParts.Length - 1; i >= 0; i--).

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks. That was so simple I never would have seen it. I am quite the novice at this stuff.
2

As you are showing the texts using the loop that swaps the items, you will not show the last item, because it's never swapped by itself.

Just show the last item after the loop:

labelBlueOne.Text += stationOneParts[0] + "\n";

Alternatively, you can display all the items outside the loop that shuffles them:

for (int i = stationOneParts.Length - 1; i > 0; i--) {
  Swap(ref stationOneParts[i], ref stationOneParts[parts.Next(i + 1)]);
}
labelBlueOne.Text = "\n" + String.Join("\n", stationOneParts);
Improve this answer

6 Comments

This works. but it was easier and cleaner to change my loop condition to (i >= 0). Thanks though.
@James: If you change the loop condition, you will do an extra swap. The last item will be swapped with the item at parts.Next(1), i.e. a random number between 0 and 0, which incidentally is always the item itself. This works, but it's a bit kludgy. I think that the cleanest solution would be to display the items outside of the loop that shuffles them; I added that alternative above.
Ok. I'll experiment with that as well. Thanks
Wow. That works. I did not know you could do something like that. This String.Join thing is new to me. I just started learning C# about 6 or 7 months ago. I am factory worker who just fiddles with this stuff as a hobby.
Wow. I looked up string.join method online. What a cool thing. I did something in java a while back and that would have helped a lot. Does java have a similar static method.
|
1

Change your loop condition to i >= 0.

Improve this answer

1 Comment

Thanks. That was so simple I never would have seen it. I am quite the novice at this stuff.
1

Simpliest approach :

        Random rnd = new Random();
        var stationOneParts = new List<string>{
        "20-packing",
        "5269-stempad",
        "5112-freeze plug",
        "2644-o'ring",
        "5347-stem",
        "4350-top packing",
        "5084-3n1 body",
        "4472-packing washer",
        "3744-vr valve o'ring",
        "2061-packing spring",
        "2037-packing nut",
        "2015-latch ring",
        "stem assembly"}.OrderBy(s => rnd.Next());

        labelBlueOne.Text = string.Join(Environment.NewLine, stationOneParts);
Improve this answer

15 Comments

That's random-ish, but not guaranteed to give a uniform distribution over the possible orderings.
@recursive: the actual source of bias is that there are only 2^32 = 4 x 10^9 possible seeds to the RNG, but there are 13! = 6 x 10^9 possible orderings of 13 elements. Therefore there are 2 billion possible final configurations that are never generated. If this is a problem then you need a stronger source of randomness. (Moreover: the default RNG seed is the current time, which introduces additional bias as the code is more likely to be run during business hours than not.)
@Guffa, @recursive: You are right to be concerned but in this case it is not a problem. The code given here is correct, modulo the other issues. When you do an "OrderBy" like this, the sorting code obtains the sort key once for each item, caches the key, and does not recompute the key. After all, the key computation might be expensive! The issue you are thinking of is non-key-based comparison sorts with randomness in the comparator. A comparison sort is required to have a consistent total ordering imposed by the comparator.
@Guffa, @recursive: That is to say, the algorithm that you are actually criticizing is this one: "myList.Sort((x, y) => random.Next(-1, 2));" -- that really is deeply wrong. There will be a new comparison done on every compared pair, and there could be n log n or even n^2 of those comparisons done, and the sort algorithm may require the comparator to be consistent. But in the algorithm that Steve gives, he generates n sort keys and that's it; we don't regenerate the keys every time a comparison needs to be done.
@Eric Lippert - In that case the order-by does introduce a bias, since it is a stable sort and will preserve the original order should any of the keys happen to be the same. That is, there is a rare bias toward maintaining the original order.
|
0

Since you mention C# 4.0, why not write is C#-ish?

using System.Linq;

// ...

    var stationOneParts = new [] { "20-packing",
        "5269-stempad",
        "5112-freeze plug",
        "2644-o'ring",
        "5347-stem",
        "4350-top packing",
        "5084-3n1 body",
        "4472-packing washer",
        "3744-vr valve o'ring",
        "2061-packing spring",
        "2037-packing nut",
        "2015-latch ring",
        "stem assembly" };

    Random rand = new Random();
    stationOneParts = stationOneParts
        .Distinct() // see subject: '... without duplicates'
        .Select(i => new { i, key=rand.Next() })
        .OrderBy(p => p.key)
        .Select(p => p.i)
        .ToArray();
Improve this answer

10 Comments

Wow, that is a lot of unnecessary parts. "parts.OrderBy(x=>rand.Next());", and you're done. Why do you feel it necessary to add a Distinct, two Selects and a ToArray to this?
@Eric: depending on the sort algorithm used, when using rand.Next() directly, it may not finish at all (since the strict weak ordering predicate is stateful, it is not deterministic, and the sort algorithm may assume it is; if it is quicksort, it will finish anyhow, but it may degrade to O(n^2) complexity). Is there a flaw in my reasoning?
@sehe: I don't really understand what you're saying, but I suspect that you have the same misapprehension that Guffa and recursive did in Steve's answer; see my comments to that answer for a lengthy discussion of this practice and why it is safe. (Moreover: if it were not safe then your extra two Selects would not make it safe. I still don't see what purpose they serve.)
@Eric: if a sort algorithm happens to compare two elements twice (bear with me), it will hurt performance and possibly correctness if the predicate returns a different value the second time. (I agree that it is unlikely, but because of .OrderBy supporting deferred execution a non-standard sorting approach might have been taken. I don't think the specification of Enumerable.OrderBy includes guarantees either way...)
But you're not supplying a predicate for the comparison, you're supplying a key for the comparison. If you were supplying a predicate, like stuff.Sort((x,y)=>-1 or 1 at random) then yes, that can cause the sort algorithm to do crazy things. But that's not what you are supplying; you're supplying a key, one key per item, not per comparison. The OrderBy doesn't re-fetch the key on every comparison; that would be both wasteful and dangerous. We have to assume that the key is expensive to produce. You are right to be thoughtful about this issue, but really, it's fine to order by a random key.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.