|
Jacek Gajek wrote: Are you a cool kid who wants to impress your friends and family with your mad skillz?
If you think you're a "cool" kid who can impress people with 1337 programming skillz0r then you really need to go outside. I knew from the beginning that programming wasn't going to make me the life of a party, it's not right for Microsoft to lie to kids this way.
My current favourite word is: Sammidge!
-SK Genius
Game Programming articles start - here[ ^]-
|
|
|
|
|
Errr.
You are aware that Alt-Space is a standard Windows key combination, aren't you?
It opens the Control Menu for the active window, by default.
Henry Minute
Do not read medical books! You could die of a misprint. - Mark Twain
Girl: (staring) "Why do you need an icy cucumber?"
“I want to report a fraud. The government is lying to us all.”
|
|
|
|
|
Henry Minute wrote: You are aware that Alt-Space is a standard Windows key combination, aren't you?
Yes, but that isn't SAS sequence and you can still capture it if you install a keyboard hook.
“Follow your bliss.” – Joseph Campbell
|
|
|
|
|
Rajesh R Subramanian wrote: and you can still capture it if you install a keyboard hook.
Hi Rajesh,
This is a bit late, I know, but I am having terrible problems with my ISP at the moment (I'm stuck on 53.6 kbps at the moment, when I can get a connection that is  ).
My point was that Alt-Space is one of the less well known keyboard shortcuts but nonetheless some people do use it (me for instance) and because of that it might be worth the OP considering an alternative. There is little that is worse than using a 'standard' shortcut only to find that the app you are using has decided to use it for formatting the C: drive. 
As far as I am aware you can capture any key combo with a global hook but whether you should is another thing.
Cheers!
Henry Minute
Do not read medical books! You could die of a misprint. - Mark Twain
Girl: (staring) "Why do you need an icy cucumber?"
“I want to report a fraud. The government is lying to us all.”
|
|
|
|
|
I'm sorry about your connection speed but I had a laugh. 
Henry Minute wrote: My point was that Alt-Space is one of the less well known keyboard shortcuts but nonetheless some people do use it (me for instance) and because of that it might be worth the OP considering an alternative.
There are many valid reasons to execute code when the user is pressing this key combo (amongst many other combos). For instance, if your application does not have a system menu, and you want to emulate it yourself. Or your application is largely ownerdrawn (we have an app where there's just one window and everything else is drawn as bitmaps in runtime) and it emulates a lot of stuff (context menu drawing, system menu drawing, cursor, etc.,) based on keyboard and mouse inputs. This can be done only with the help of a hook. And this is not going to affect the way other applications work (you execute your code, only if your window is active).
Henry Minute wrote: As far as I am aware you can capture any key combo with a global hook
Not any key combo. The SAS (Ctrl+Alt+Del) key combo is not something that can be trapped because it triggers a hardware interrupt that isn't notified of outside the ring0 level. (OK, may be that can as well be trapped, but that will require ninja windows programming skills). Even with ninja skills, it is almost impossible to trap it on x64 versions of Windows, because of Kernel Patch Protection.
“Follow your bliss.” – Joseph Campbell
|
|
|
|
|
Rajesh R Subramanian wrote: I'm sorry about your connection speed but I had a laugh
You are just evil. 
Rajesh R Subramanian wrote: For instance, if your application does not have a system menu, and you want to emulate it yourself.
True, I hadn't considered that case. Nonetheless the OP should be made aware, if he wasn't already, of the existing use.
Rajesh R Subramanian wrote: (OK, may be that can as well be trapped, but that will require ninja windows programming skills)
As a coder currently at the Noneja level I'll leave that stuff to you guys.
Henry Minute
Do not read medical books! You could die of a misprint. - Mark Twain
Girl: (staring) "Why do you need an icy cucumber?"
“I want to report a fraud. The government is lying to us all.”
|
|
|
|
|
AndyASPVB wrote: In my application, I need capture when a user presses the key combination "alt-space". Can someone show me how to do this, please?
Hi,
You will need to write a keyboard hook for this purpose. Refer to the following article:
Processing Global Mouse and Keyboard Hooks in C#[^]
“Follow your bliss.” – Joseph Campbell
|
|
|
|
|
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 n-1, 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 read-to-use out-of-the-box nice-and-elegent 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 length-5 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 skip-array, 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 non-removed 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 over-inquisitive 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 n-th digit of a factoriadic.
Greetings - Jacek
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
