
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





I want to automated call function "save as" and choise "save as type = webpage completed..." from Webbrowser Control (Windows Forms, C#).
I found the source code in link "http://www.codeproject.com/KB/shell/iesaveas.aspx?msg=1101501" but i can't understand C++. From this code i want to build a funtion DownloadHTMLCompleted(String URI, String FileName) by C++ or C#, then call this funtion from C#.
Help me!





Nguyễn Đức Thiện wrote: but i can't understand C++.
Nguyễn Đức Thiện wrote: build a funtion ... by C++
You say you don't understand C++ but want to create a function in C++
only two letters away from being an asset





yes!
I can't understand C++ but i can call this from C# (because i think may be anyone help me by C++, this way is faster)





Message Closed
modified 23Nov14 7:31am.




