Jump to content
• Advertisement

# What's the name of this algorithm?

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

If you intended to correct an error in the post then please contact us.

## 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 ("[color="#ff0000"]QueryPermutations") 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:

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

For example, given the input 'A B C D', the output would be:

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

##### Share on other sites
Advertisement
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 binary counting can give you some ideas then. I have no specific name for it myself though.

#### Share this 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.

Interesting; that would've been a simpler way of viewing the problem had I thought of that (I started by looking at functions like std::next_permutation, 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

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

#### Share this post

##### 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 this post

##### Share on other sites
What's being computed here is called combinations without repetitions .
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 combinations and permutations; they are completely different concepts that are only vaguely connected by theory.

#### Share this post

##### Share on other sites

• Advertisement
• Advertisement

• ### Popular Contributors

1. 1
2. 2
Rutin
23
3. 3
JoeJ
20
4. 4
5. 5
• Advertisement

• 29
• 40
• 23
• 13
• 13
• ### Forum Statistics

• Total Topics
631740
• Total Posts
3001962
×

## Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!