当前位置: 动力学知识库 > 问答 > 编程问答 >

c# - Arraylist Shuffle algorithm using a key

问题描述:

How would I code a reversible shuffle algorithm in C# ArrayList which uses a key to shuffle and can be reversed to the original state?

网友答案:
    private class myItem
    {
        public Int32 ID { get; set; }
        public Int32 Rand { get; set; }
        public String Value { get; set; }

    }

    private void Main(object sender, EventArgs e)
    {

        string[] array = new string[] { "alpha", "beta", "gamma", "delta" };
        List<myItem> myArray = addKeys(array);//adds keys to array required for randomization and reversing
        string[] randomarray = randomize(myArray);
        string[] reversedarray = reverse(myArray);

    }
    private List<myItem> addKeys(string[] array)
    {
        Random random = new Random();
        List<myItem> myArr = new List<myItem>();
        for (int i = 0; i < array.Length; i++)
        {
            myArr.Add(new myItem { ID = i, Rand = random.Next(), Value = array[i] });

        }
        return myArr;
    }
    private string[] randomize(List<myItem> myArray)
    {
        return (from item in myArray
                         orderby item.Rand
                         select item.Value).ToArray();
    }
    private string[] reverse(List<myItem> myArray)
    {
        return (from item in myArray
                         orderby item.ID
                         select item.Value).ToArray();
    }
网友答案:

You can use KeyValuePair. You can get a detailed explanation here on the following site: http://www.dotnetperls.com/shuffle

However as you want to reverse it, I suggest using a DataTable. In first column you can have original sort order (integers may be), in second column you can have random numbers created. In third column you can have the values you need to sort. Then use the sorting by second column to shuffle and then sort it by first column to revert it.

网友答案:

Shuffling an array is done by swapping the elements inside the array several times.

If you take an array, swap the elements, then swap them again, but in the reverse order you swapped them initially, you get the original array back.

These shuffling positions can be generated from PRNG (Pseudorandom number generator). For a given seed, a PNRG will always generate the same numbers : that will be your "key".

Here is some code using that idea (Fisher Yates is used for the shuffle):

public static void Shuffle(ArrayList list, int seed, bool reverse = false)  
{           
    Random rng = new Random(seed); 
    List<Tuple<int, int>> swaps = new List<Tuple<int, int>>();
    int n = list.Count;  

    //prepare swapping positions 
    while (n > 1) {  
        n--;  
        int k = rng.Next(n + 1);  
        swaps.Add(new Tuple<int, int>(k, n));
    }

    //reverse if needed
    if(reverse)
        swaps.Reverse();

    //swap the items
    foreach(Tuple<int, int> swap in swaps)
    {       
        object value = list[swap.Item1];  
        list[swap.Item1] = list[swap.Item2];  
        list[swap.Item2] = value;
    }
}

Usage :

ArrayList a = new ArrayList();
int key = 2742;

Shuffle(a, key);
Shuffle(a, key, true);

Note that if you don't want the key to be an integer, but a string, you can use exact same method but the integer using "somekey".GetHashCode()

网友答案:

Here is a simple way that only requires you to store your "key", as well as not change the shuffling algorithm.

It does not matter which shuffle algorithm you use as long as you can reproduce it, meaning that if you use the same key or seed, and run the shuffle algorithm twice, it will shuffle the exact same way both times.

If you can do that, using a key, or a seed to your shuffle algorithm, then you're good to go.

All you have to do in order to reverse it is to shuffle an array of integers, where the values in the array before the shuffle corresponds to the index of each element. After shuffling, with the same key or seed as above, you now have a shuffled copy where each value is the index of the original placement in the unshuffled array.

Let me give you an example.

Let's assume an array of 4 integers, values 0 through 3 (element at index 0 has a value of 0, element at index 1 has a value of 1, and so on).

Shuffle this, to obtain this array: 3, 1, 2, 0.

This now means that the first element of the shuffled array used to be at index 3, the second element was at index 1, the third at index 2, and the fourth at index 0.

分享给朋友:
您可能感兴趣的文章:
随机阅读: