0

I have an array of integers, for example: a[1,2,3]. I would like to get all possible combinations of these numbers where they don't repeat, possibly with recursion.

I saw something like this done with strings here: Get all combinations without duplicates but don't know how to adapt it to integers without using any standard algorithms.

So I would like something like this as an output: {1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}

Thanks in advance!

Ge To
  • 107
  • 5
  • 4
    for permutations use `std::next_permutation`, for combinations use it also ;) – 463035818_is_not_an_ai Nov 08 '20 at 18:32
  • 1
    @idclev463035818 the tag `recursion` (and other clues) suggests that this must be done without use of the std algorithms – Vlad Feinstein Nov 08 '20 at 18:44
  • The _Possible Implementation_ session from the [cppreference](https://en.cppreference.com/w/cpp/algorithm/next_permutation) may give some clues on how you can implement your version from scratch. – gallo Nov 08 '20 at 18:47
  • @VladFeinstein you can use `std::next_permutation` also with recursion. I know that often exercises have weird requirements, like disallowing standard algorithms, but that doesn't make me assert such weird requirements when OP does not mention them. If standard algorithms are out it shuold be mentioned in the question – 463035818_is_not_an_ai Nov 08 '20 at 18:55
  • Yes, all standard algorithms are out. Thanks for telling me since I didn't know... I got a decent bit of code from here: https://www.geeksforgeeks.org/heaps-algorithm-for-generating-permutations/ I just need to modify it somehow that it also outputs the possibilities where it doesn't use all the numbers. – Ge To Nov 08 '20 at 19:02
  • please include your code in the question together with compiler error or output vs expected output so we can help you with your code (see [mcve]) – 463035818_is_not_an_ai Nov 08 '20 at 19:05
  • and please clarify if you want combinations or permutations, the terms are confused often and the site you linked is for permutations but your question asks for combinations – 463035818_is_not_an_ai Nov 08 '20 at 19:07
  • I want combinations. Something like this: https://stackoverflow.com/questions/49469238/get-all-combinations-without-duplicates But I think I can do it myself from this. I know I worded my question really badly. So if I have an array for intiger: `a[1,2,3] ` I get all the combinations: `{1},{2},{3},{1,2}.{2,3},{1,3},{1,2,3}`. I just got confused a bit. – Ge To Nov 08 '20 at 19:49
  • well your question wasnt actually worded that badly, its the answers that confused permutations for combinations ;) – 463035818_is_not_an_ai Nov 08 '20 at 23:10
  • you do not have to repost the same question btw. If your question is unclear then better improve it instead of posting the same / similar question again – 463035818_is_not_an_ai Nov 08 '20 at 23:11

2 Answers2

2

You can achieve all permutations of a list with comparable elements using std::next_permutation from <algorithms> library.

The cppreference has a nice article about this: https://en.cppreference.com/w/cpp/algorithm/next_permutation

We can use the code example to apply to your question.

#include <algorithm>
#include <string>
#include <iostream>
#include <vector>

void print_vector(const std::vector<int>& array) {
    for (const int item : array)
    {
        std::cout << item << " ";
    }
    std::cout << std::endl;
}
 
int main()
{
    std::vector<int> a({ 5,1,8,7,2 });
    std::sort(a.begin(), a.end());
    do {
        print_vector(a);
    } while(std::next_permutation(a.begin(), a.end()));
}
gallo
  • 546
  • 7
  • 10
1

You can use std::next_permuation to achieve your goal. Keep in mind you need to sort the array before starting to use this algorithm. The loop will exit the first time std::next_permuation returns false. If the array isn't sorted by the time you start std::next_permuation loop, you will miss all the arrays that are lexicographically lower than the current one when entering the loop.

    int main()
    {
        std::vector<int> a = { 5,1,8,7,2 };
        std::sort(a.begin(), a.end());
        std::cout << "Possible permutations :\n";
        do {
            for (auto o : a)
                std::cout << o;
            std::cout << std::endl;
        } while (std::next_permutation(a.begin(), a.end()));
        return 0;
    }
user
  • 934
  • 6
  • 17