# What's the name of this algorithm?

This topic is 2343 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 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 on other sites
What you've got there is the "power set" of your set of objects.

##### Share on other sites
Perfect! Thanks alot.

That is exactly what I have, except I skip the 'Empty Set'. It makes an excellent function name too.

##### 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 on other sites

This topic is 2343 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Create an account

Register a new account

• ### Forum Statistics

• Total Topics
628682
• Total Posts
2984210

• 10
• 13
• 13
• 9
• 10