Random Permutation Interface
-
I would like to create an extension method that randomly permutes the contents of an ordered list (preferably in-place). This is what I have so far:
public static class PermuteExtensions {
public void Permute<T, U>(this T list) where T : IEnumerable<U> { // Create a copy of the input array U\[\] tempArray = list.ToArray(); long arraySize = tempArray.LongLength; // Create a permutation of indexes, so list\[j\] = tempArray\[indexes\[j\]\] long\[\] indexes = new long\[arraySize\]; // ... // Assign the new values to the existing ordered collection long j = 0; IEnumerator<U> enumer = list.GetEnumerator(); while (enumer.GetNext()) { // Uh-oh, cannot assign to enumer.Current! enumer.Current = tempArray\[indexes\[j++\]\]; } }}
There are two problems with this approach: 1. I cannot figure out how to modify the contents of an IEnumerable object. 2. How to specify the constraint on T such that I allow this method to be called on the ordered collections (IList, Stack, Queue, List, LinkedList), but not on the unordered collections (IDictionary, Dictionary, ISet, Set). It is NOT a firm requirement that this be an in-place algorithm. However, I don't know how to construct a new T object that offers a consistent way to add objects for all of the ordered collections listed above. Thanks,
Sounds like somebody's got a case of the Mondays -Jeff
You can't modify an IEnumerable. You can't modify a Queue or a Stack via array indexing, either. So I don't think it's reasonable to try to do this in place except with an IList. List<T>, Stack<T> and Queue<T> all have a constructor that takes an argument of type IEnumerable<T>, so you could potentially build a new instance of the same type that you started with. However, considering you are already making a copy of the complete contents of the collection, and storing them in a temporary array, why not just return a List<T> with those items?
-
You can't modify an IEnumerable. You can't modify a Queue or a Stack via array indexing, either. So I don't think it's reasonable to try to do this in place except with an IList. List<T>, Stack<T> and Queue<T> all have a constructor that takes an argument of type IEnumerable<T>, so you could potentially build a new instance of the same type that you started with. However, considering you are already making a copy of the complete contents of the collection, and storing them in a temporary array, why not just return a List<T> with those items?
BobJanova wrote:
You can't modify a Queue or a Stack via array indexing
Damn, I should have mentioned that point. My 5 for that.
*pre-emptive celebratory nipple tassle jiggle* - Sean Ewington
"Mind bleach! Send me mind bleach!" - Nagy Vilmos
CodeStash - Online Snippet Management | My blog | MoXAML PowerToys | Mole 2010 - debugging made easier
-
Skippums wrote:
1. I cannot figure out how to modify the contents of an IEnumerable object.
As you've discovered, you can't change the object you're enumerating over because you'd invalidate the enumerator. What you could do, though, is not use the enumerator - instead, you can iterate over the collection by index using a for loop, and update the underlying array using that instead. So, your loop becomes something like:
for (int i = 0; i < list.Count; i++)
{
list[i] = tempArray[indexes[j++]];
}Note that this isn't possible for something like a
LinkedList. As for the constraint - I'm afraid that you can't do this at the constraint level. You'd have to test this in the actual method body and raise an exception if it was the wrong type.*pre-emptive celebratory nipple tassle jiggle* - Sean Ewington
"Mind bleach! Send me mind bleach!" - Nagy Vilmos
CodeStash - Online Snippet Management | My blog | MoXAML PowerToys | Mole 2010 - debugging made easier
Pete O'Hanlon wrote:
Note that this isn't possible for something like a
LinkedList.This is exactly why I said he'd have to wrap each collection he wanted to do this to.
A guide to posting questions on CodeProject[^]
Dave Kreskowiak -
I would like to create an extension method that randomly permutes the contents of an ordered list (preferably in-place). This is what I have so far:
public static class PermuteExtensions {
public void Permute<T, U>(this T list) where T : IEnumerable<U> { // Create a copy of the input array U\[\] tempArray = list.ToArray(); long arraySize = tempArray.LongLength; // Create a permutation of indexes, so list\[j\] = tempArray\[indexes\[j\]\] long\[\] indexes = new long\[arraySize\]; // ... // Assign the new values to the existing ordered collection long j = 0; IEnumerator<U> enumer = list.GetEnumerator(); while (enumer.GetNext()) { // Uh-oh, cannot assign to enumer.Current! enumer.Current = tempArray\[indexes\[j++\]\]; } }}
There are two problems with this approach: 1. I cannot figure out how to modify the contents of an IEnumerable object. 2. How to specify the constraint on T such that I allow this method to be called on the ordered collections (IList, Stack, Queue, List, LinkedList), but not on the unordered collections (IDictionary, Dictionary, ISet, Set). It is NOT a firm requirement that this be an in-place algorithm. However, I don't know how to construct a new T object that offers a consistent way to add objects for all of the ordered collections listed above. Thanks,
Sounds like somebody's got a case of the Mondays -Jeff
Have a look at this Non-recursive Permutations and Combinations[^]. And this LimitedQueue[^] can give insight into indexing a Queue.
-
You can't modify an IEnumerable. You can't modify a Queue or a Stack via array indexing, either. So I don't think it's reasonable to try to do this in place except with an IList. List<T>, Stack<T> and Queue<T> all have a constructor that takes an argument of type IEnumerable<T>, so you could potentially build a new instance of the same type that you started with. However, considering you are already making a copy of the complete contents of the collection, and storing them in a temporary array, why not just return a List<T> with those items?
As to the, "why not just return a list", the answer is that I feel like I should return the same type that is passed in. No particular reason, in fact I really only need this to work on a list, but prefer to write code that is reusable whenever possible.
Sounds like somebody's got a case of the Mondays -Jeff
-
I would like to create an extension method that randomly permutes the contents of an ordered list (preferably in-place). This is what I have so far:
public static class PermuteExtensions {
public void Permute<T, U>(this T list) where T : IEnumerable<U> { // Create a copy of the input array U\[\] tempArray = list.ToArray(); long arraySize = tempArray.LongLength; // Create a permutation of indexes, so list\[j\] = tempArray\[indexes\[j\]\] long\[\] indexes = new long\[arraySize\]; // ... // Assign the new values to the existing ordered collection long j = 0; IEnumerator<U> enumer = list.GetEnumerator(); while (enumer.GetNext()) { // Uh-oh, cannot assign to enumer.Current! enumer.Current = tempArray\[indexes\[j++\]\]; } }}
There are two problems with this approach: 1. I cannot figure out how to modify the contents of an IEnumerable object. 2. How to specify the constraint on T such that I allow this method to be called on the ordered collections (IList, Stack, Queue, List, LinkedList), but not on the unordered collections (IDictionary, Dictionary, ISet, Set). It is NOT a firm requirement that this be an in-place algorithm. However, I don't know how to construct a new T object that offers a consistent way to add objects for all of the ordered collections listed above. Thanks,
Sounds like somebody's got a case of the Mondays -Jeff
Thanks everyone for the feedback! The solution I went with is the following:
public static class Permutation {
// Random number generator private static Random rand = new Random(); // Permute a collection of objects, returning an array public static T\[\] Permute<T>(IEnumerable<T> list) { // Create a copy of the input array T\[\] permArray = list.ToArray(); long arraySize = permArray.LongLength; // Create a permutation of indexes long\[\] perm = Permutation.Random(arraySize); // Assign the new values to the existing ordered collection long i = 0; foreach (T item in list) { permArray\[perm\[i++\]\] = item; } // Return the permuted array return permArray; } // Generates a random permutation of the integers in the range \[0, size) public static long\[\] Random(long size) { long\[\] perm = new long\[size\]; lock(rand) { for (long i = size - 2; i >= 0; --i) { // I implemented the extension method Random.NextInt64 perm\[i\] = rand.NextInt64(size - i); for (long j = i + 1; j < size; ++j) { if (perm\[i\] <= perm\[j\]) ++perm\[j\]; } } } return perm; }}
This will allow a client a way to get a permutation from a set or dictionary as well. Thanks again for the ideas!
Sounds like somebody's got a case of the Mondays -Jeff
-
Thanks everyone for the feedback! The solution I went with is the following:
public static class Permutation {
// Random number generator private static Random rand = new Random(); // Permute a collection of objects, returning an array public static T\[\] Permute<T>(IEnumerable<T> list) { // Create a copy of the input array T\[\] permArray = list.ToArray(); long arraySize = permArray.LongLength; // Create a permutation of indexes long\[\] perm = Permutation.Random(arraySize); // Assign the new values to the existing ordered collection long i = 0; foreach (T item in list) { permArray\[perm\[i++\]\] = item; } // Return the permuted array return permArray; } // Generates a random permutation of the integers in the range \[0, size) public static long\[\] Random(long size) { long\[\] perm = new long\[size\]; lock(rand) { for (long i = size - 2; i >= 0; --i) { // I implemented the extension method Random.NextInt64 perm\[i\] = rand.NextInt64(size - i); for (long j = i + 1; j < size; ++j) { if (perm\[i\] <= perm\[j\]) ++perm\[j\]; } } } return perm; }}
This will allow a client a way to get a permutation from a set or dictionary as well. Thanks again for the ideas!
Sounds like somebody's got a case of the Mondays -Jeff
Nice work ! The question of what you'd need to do randomly re-order a Dictionary<T,V> remains of interest to me. best, Bill
"When it comes to atoms, language can be used only as in poetry. The poet, too, is not nearly so concerned with describing facts as with creating images." Niels Bohr
-
Nice work ! The question of what you'd need to do randomly re-order a Dictionary<T,V> remains of interest to me. best, Bill
"When it comes to atoms, language can be used only as in poetry. The poet, too, is not nearly so concerned with describing facts as with creating images." Niels Bohr
Dictionaries don't have order anyway.
-
Thanks everyone for the feedback! The solution I went with is the following:
public static class Permutation {
// Random number generator private static Random rand = new Random(); // Permute a collection of objects, returning an array public static T\[\] Permute<T>(IEnumerable<T> list) { // Create a copy of the input array T\[\] permArray = list.ToArray(); long arraySize = permArray.LongLength; // Create a permutation of indexes long\[\] perm = Permutation.Random(arraySize); // Assign the new values to the existing ordered collection long i = 0; foreach (T item in list) { permArray\[perm\[i++\]\] = item; } // Return the permuted array return permArray; } // Generates a random permutation of the integers in the range \[0, size) public static long\[\] Random(long size) { long\[\] perm = new long\[size\]; lock(rand) { for (long i = size - 2; i >= 0; --i) { // I implemented the extension method Random.NextInt64 perm\[i\] = rand.NextInt64(size - i); for (long j = i + 1; j < size; ++j) { if (perm\[i\] <= perm\[j\]) ++perm\[j\]; } } } return perm; }}
This will allow a client a way to get a permutation from a set or dictionary as well. Thanks again for the ideas!
Sounds like somebody's got a case of the Mondays -Jeff
Skippums wrote:
make the method that returns the array public
That sounds like a better idea. And/or something like a
RandomSequence(int n)that returns an array of0..nin random order. -
Skippums wrote:
make the method that returns the array public
That sounds like a better idea. And/or something like a
RandomSequence(int n)that returns an array of0..nin random order.Actually, I did end up making my method that returns a T[] public, and deleted all the wrapper methods. I figured that if clients want the result in a stack, queue, list, etc., they can build it themselves with a simple constructor call. Plus, having an extension method on IEnumerable allows a client to get a permutation from a set, which seems like it could be a useful operation.
PIEBALDconsult wrote:
something like a
RandomSequence(int n)that returns an array of0..nin random orderActually, in the code I posted, a client can get this with a call to
long[] Permutation.Random(long size). I suppose I could add the same code for int, but don't really see the point. I also thought about allowing a client to get a specific permutation, but that only works for permutations up to length 20 (since 21! > 264), unless I include a large integer library.Sounds like somebody's got a case of the Mondays -Jeff