Sign in to follow this  
Servant of the Lord

What's the name of this algorithm?

Recommended Posts

I wrote an algorithm a while back, to get a specific subset of all the permutations of a series of objects.

I'm now reorganizing part of my code base, and so I'm separating the algorithm into a standalone function instead of being part of a class that was using it, to make the function easier to reuse. I don't know what to call the function, and since I'm sure this type of thing has been done hundreds of times before, I feel it'd be good to name it by the standard name everyone else uses. However, since I wrote the algorithm myself, I don't know what name others commonly give to it.

Currently, the function is just named 'GenerateQueryPermutations()', but there are two problems with that name. 1) I'm tying the name of the function to one specific use ("[b][color="#ff0000"]Query[/color][/b]Permutations") of the function, not it's generalized use. 'GeneratePermutations()' is more general. 2) There are multiple different subsets of permutations, and this function is specifically designed to generate a certain subset of them, and not generate every subset, so 'GeneratePermutations()' is a misnomer, since it really only generates a specific group of permutations.

Here's my description of the function:

[quote][i]Given a series of elements, like 'A B C D', this function returns a list of strings with every possible variation,[/i]
[i]excluding permutations using the same element twice ('A B A' uses 'A' twice), and excluding permutations[/i]
[i]that have already occured, which contain the same elements but merely in different orders. (If "A B C" already[/i]
[i]occured, then "A C B", "B C A", and similiar results wont re-occur).[/i]

[i]For example, given the input 'A B C D', the output would be:[/i]

A B C D
A B C
A B D
A B
A C D
A C
A D
A
B C D
B C
B D
B
C D
C
D[/quote]

Also, I know I'm misusing the word 'algorithm'. The word 'algorithm' is used to describe (one of) the processes used to get to the result from a given input, is that correct? So, is there a specific term used to describe the 'result' of an algorithm? Like the 'result' of multiplication is the 'product', and etc... what is the 'result' of an algorithm called? Wikipedia seems to call it a 'function'. That is to say, "An algorithm calculates a function", or "An algorithm calculates a function's value" (Which of those two is correct?). Is there another name for it?

I want to name this function after the specific type of result it produces, not the process it goes through to reach that result. Looking at the above example input and output, what would you recommend I name the function?

Share this post


Link to post
Share on other sites
This is nothing more than binary counting. You have four slots, and you want to get all combinations of all slots being on and off. So for 4 slots, just make a for-loop from 0 to 2[sup]4[/sup]-1, and the bit pattern of the loop variable indicates the slots being on or off.

Just noticed that you're asking for a name of the algorithm, not how to do it. But perhaps [i]binary counting[/i] can give you some ideas then. I have no specific name for it myself though.

Share this post


Link to post
Share on other sites
[quote name='Brother Bob' timestamp='1310676253' post='4835425']
This is nothing more than binary counting. You have four slots, and you want to get all combinations of all slots being on and off. So for 4 slots, just make a for-loop from 0 to 2[sup]4[/sup]-1, and the bit pattern of the loop variable indicates the slots being on or off.
[/quote]
Interesting; that would've been a simpler way of viewing the problem had I thought of that (I started by looking at functions like [url="http://www.cplusplus.com/reference/algorithm/next_permutation/"]std::next_permutation[/url], but realized it gave certain results that I didn't want, so I wrote it from the 'generate permutations' mindset).

But I already have a function that produces the results, I just don't know how to name the function in a descriptive way.

Share this post


Link to post
Share on other sites
What you've got there is the "power set" of your set of objects.

Share this post


Link to post
Share on other sites
What's being computed here is called [b][url="http://en.wikipedia.org/wiki/Combination"][i]combinations without repetitions [/i][/url][/b].
Choosing only the subset of a certain size (e.g. 3 out of 4: ABC ABD ACD BCD from ABCD) is the traditional restriction, but if you want all sizes together counting in binary is a perfectly good way to produce them.
Please don't confuse [b]combinations [/b]and [b]permutations[/b]; they are completely different concepts that are only vaguely connected by theory.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this