
Hi!
I am not sure how to express what I need. However...
I've got a code which generates all permutations of an array of numbers 0 to n1, which can be used to generate permutations of any array, since every element can be mapped to it's index and vice versa.
Here it is:
public IEnumerable<int[]> GetPermutations()
{
if (n == 1)
{
yield return indexes;
yield break;
}
var generator = new PermutationGenerator(n  1);
bool even = false;
foreach (int[] permutation in generator.GetPermutations())
{
if (even)
for (int i = 0; i < n; i++)
yield return InsertN(permutation, i);
else
for (int i = n  1; i >= 0; i)
yield return InsertN(permutation, i);
even = !even;
}
} In an algorithm I am currently writing, sometimes it is good to skip some permutations. E.g. I have reached [12345678], and realize that I don't need any perm. which starts with [123.....], so I would like to skip 5! permutations and go in one step to [124.....]. It basically means that I would like to put a "return " in a given level of recursion. The code would look like this I suppose:
foreach (int[] permutation in GetPermutations())
{
SkipPermutations(4);
} Of course I will not be satisfied with a solution like running empty for loop to skip a number of permutations.
The problem here is recursion. I have inspected an Enumerator class generated by a compiler using Reflector and it was very complicated. Any Ideas how to achieve it a simple and elegant way?
Thanks in advance 
Greetings  Jacek





Ok, my brain is kind of winding down, it being Friday and all, so I can't quite wrap it around your algorithm right now... But for skipping entries in the enumeration itself...
Basically, foreach is a shortcut for a more wordy but not very complicated code block:
IEnumerator<int[]> en = GetPermutations().GetEnumerator()
while (en.MoveNext())
{
int[] permutation = en.Current;
}
If you write this out yourself, you have a reference to the enumerator, so you can do this:
public bool SkipPermutations(IEnumerator en, int count)
{
for(;count > 0; count)
if (!en.MoveNext()) return false;
return true;
}
Then you can just put this in the middle of your foreach:
if (!SkipPermutations(en, 4)) break;
The trick, of course, is that if you skip past the end of the enumeration, you'll get an exception... So you have to keep checking to see if you're at the end.





Thanks for answer, but...
I wrote: Of course I will not be satisfied with a solution like running empty for loop to skip a number of permutations.
Sorry, but I need to reduce time complexity by skipping permutations. That solution is pointless since it does these iterations anyway.
Greetings  Jacek





I was thinking of that, but like I said, hard to wrap my brain around your algorithm right about now...
What you could do is set a boolean flag on your generator class in the SkipPermutations function... And in GetPermutations(), you can "yield return 0" instead of running a block of code whenever you want to skip an entry. I'm not sure where exactly to put it though.
Basically MoveNext() will continue GetPermutations() until it hits the next "yield" statement. If it's a "yield return", it'll set the Current property to the result and return true... If it's a "yield break", it'll return false. So you just need GetPermutations() to "yield return 0" until the skip flag is turned off.





Ian Shlasko wrote: a boolean fla
Yeach I though about it before, but I have encountered implementation difficulties. Fortunately, harold posted an almost readtouse outofthebox niceandelegent solution.
Greetings  Jacek





I know it doesn't answer the question, but may I suggest factoradic numbers[^]?
edit: then you could skip x iterations by just adding x to the "permutation number" Last modified: 24mins after originally posted 





Very interesting read... I wonder how practical it would be in these terms though, given the processing needed to keep resizing a list in that manner... With an array, you'd have to either keep resizing it or mark+skip zeroes every time you pick out a number... With a linked list, you've got ridiculous allocation times...
There has to be a data structure that'd scale well enough, because those factoradic numbers seem like a great way to iterate...





Resizing..? Have you looked at the implementation, btw?
edit: no offense, of course
IME they are alright, reasonably fast, perfect to impress peers with, etc





I read through the Wikipedia article... Didn't see the implementation.
Once you actually generate the factoradic number, you still need to grab the items from the array... Like in their example:
Factoradic: 4041000
Array: 0,1,2,3,4,5,6
Step 1: Take element #4 and remove it from the array
Array: 0,1,2,3,5,6 < Resized, which would be too slow for an array OR
Array: 0,1,2,3,_,5,6 < Marked to skip
Step 2: Take element #0 and remove it
Array: _,1,2,3,_,5,6
Step 3: Take element #4 and remove it
Array: _,1,2,3,_,5,_
Can see the issue in the third step... The #4 element is actually the sixth because we removed two... So you can't just access an array index (First address + (element size x index)), which would be lightning quick... You have to count through the array like you're iterating through a linked list.
So basically, once you generate the factoradic, building the permutation is 6+5+4+3+2+1 (In whatever order) steps, or n(n+1)/2... an O(n^2) operation.
(The only good part about that method is that you can actually use a boolean array to mark the flags and clear it in one memory operation for the next pass)
Then if you're generating ALL possible permutations, it's an O(n^3) operation.
So I'm trying to think of a data structure that would chop that n^2 down a bit.





You don't have to do it like that, there is a nice trick, as seen in line 71 to 75 of:
This implementation[^]





No, that's generating the factoradic... I mean actually turning that into the resulting permutation... The implementation you posted does it like this:
this.data[n  1] = 1;
for (int i = n  2; i >= 0; i)
{
this.data[i] = temp[i];
for (int j = i + 1; j < n; ++j)
{
if (this.data[j] >= this.data[i])
++this.data[j];
}
}
(temp is the modified factoradic)
Assuming this works... It's the same complexity as what I posted, with the first loop rolled out. "i" counts backwards, and "j" counts from "i" to the end... So for a length5 number, "i" goes from 4 to 0, and "j" (the inner loop) goes 1,2,3,4,5...
I'm not saying it isn't a nice algorithm... That inner loop would be pretty quick... But it's still going to scale with the square of the array size, and I'm trying to think of a faster route.





Oh right, sorry
What if you make a binary tree from the elements?
edit: probably a stupid idea, but I was thinking like: ok you can delete in constant time (unbalancing is not a problem) and you can retrieve the element from any index in logaritmic time, this all times n gives O(n log n) which is better than O(n^2)





With a bintree, wouldn't deleting also be O(log n)? But retrieval gets worse, not better... You aren't searching for element N, which would be easy, but the Nth element... Element #6 could be the 4th one, and a bintree doesn't really support that kind of operation very easily, unless I'm missing something.
Maybe with a sort of skiparray, we could cut a little off the iteration...
struct
{
int ElementValue
int SkipForward
int SkipBackwards
}
So for deleting, you jump straight in... But also jump forwards and backwards to "connect" the adjacent nonremoved elements. Then when you need the Nth element, instead of just doing a flat iteration, you follow the SkipForward to jump through the array like a linked list.
For efficiency, could actually use three arrays instead of a struct, so between runs it's trivial to zero out the two skip arrays without changing the ElementValue array.
Still O(n^2), but less hops... It would take more operations for each removal, but with a large enough set, it might still be faster. An improvement, but not a generation leap, so to speak.





Maybe there is no better way?





I don't give up that easily... Have to think on this a while.





Thanks!
After a few modification that implementations works for me. What I needed was a lexicographical order permutation generator. Now I have to implement it myself to learn how to answer overinquisitive teacher's questions.
Thanks again 
Greetings  Jacek





Here are my modifications[^] which
1. Use C# 2.0 goodies
2. All operations are in situ now.
Greetings  Jacek





harold aptroot wrote: edit: then you could skip x iterations by just adding x to the "permutation number"
In terms of the factoriadic numbers, I was interested in skipping n! iterations, which means adding 1 to nth digit of a factoriadic.
Greetings  Jacek





OK, I have given up my algoritm and have been using an implementation posted by harold (thanks mate). I have added two methods:
public void First(int[] beginning, int order)
{
var check = new bool[order];
for (int i = 0; i < beginning.Length; i++)
{
check[beginning[i]] = true;
data[i] = beginning[i];
}
int checkI = 0;
for (int i = beginning.Length; i < order; i++)
{
while (check[checkI])
checkI++;
data[i] = checkI;
checkI++;
}
}
and
public static IEnumerable<Permutation> GetPermutations(int order)
{
var permutation = new Permutation(order);
while ((permutation = permutation.GetSuccessor()) != null)
yield return permutation;
}
And the usage:
var perm = new Permutation(5);
var beginning = new[] { 1 };
foreach (Permutation permutation in Permutation.GetPermutations(5))
{
if (permutation.StartsWith(beginning))
{
permutation.First(new [] { 2}, perm.Order);
}
Console.WriteLine("{0} {1} {2} {3} {4}", permutation[0], permutation[1], permutation[2], permutation[3], permutation[4]);
}
The code above skips all permutations in form [1....].
Thanks!
Greetings  Jacek





Good I'm glad it solved your problem
Sorry for the lack of replies btw, I was sleeping lol





Where is the best place to write application files on Vista or W7? I'm looking for a global (accessible by all users) location to create a directory structure so I can write log files, settings, and user created files into separate directories.
My original idea was to use subdirectories under my root program directory but Program Files is locked by default and I don't want to disable the UAC. I've heard issues with the virtualization that some programs will see the virtual directory and some won't.
I thought about using the Users\Public folder, but I wasn't sure if this is the right place.
Is is better/possible to elevate my permissions so I can write to the Program Files directory?
Thanks for any help pointing me in the right direction.
Brad
Deja Moo  When you feel like you've heard the same bull before.





I usually store things on a peruser basis, but I think Environment.GetFolderPath(Environment.SpecialFolder.CommonApplicationData) is supposed to give you exactly that, regardless of which OS you're on.





Thanks for your help... and making me feel very ignorant.
I was looking at the list that had all of the special folders and saw CommonProgramFiles, COmmonDocuments, CommonPrograms, etc. After seeing your response, I looked at the list again and I bet you'll never guess what the second one was.
I was looking for something referencing public.
Brad
Deja Moo  When you feel like you've heard the same bull before.





Heh, don't feel bad... There's a ridiculous amount of content in the framework... I've done the same thing in other parts.





Hi there,
I know how to control the master volume of a system, but how I should do it individually for each speaker?  I didn't found any hint so far.
E.G.: A 5.1 or 7.1 System has 6/8 speakers and I want to reduce the volume of center and sub but increase the back speakers for example.
I'm creating an media player where I want to control the individual volume of those speakers.
I appreciate your help!
Zsolt / Germany




