Recursion of for's

Question

I'm tried to figure out how to do it for quite of time and its not working as intended; I'm writing a code where there is 1 to k numbers, I need to find all possible combination without repeats. e.g. for 3: 1, 2, 3, 12, 13.

Example for counting 4-digits numbers with 1, 2, 3, 4, 5.

int k = 5;
for (int p = 0; p < k; p++)
{
    for (int i = p+1; i < k; i++)
    {
        for (int j = i + 1; j < k; j++)
        {
            for (int h = j + 1; h < k; h++)
            {
                cout << p + 1 << i + 1 << j + 1 << h + 1 << endl;
            }
        }
    }
}

And there is example for 3-digits number with 1, 2, 3.

int k = 4
for (int p = 0; p < k; p++)
{
    for (int i = p+1; i < k; i++)
    {
        for (int j = i + 1; j < k; j++)
        {
            cout << p + 1 << i + 1 << j + 1 << endl;
        }
    }
}

I think that to count n-digits possible position without repeat i need n for's. And i don't know how to do it without recursion which don't work when i do it. My goal to get recursion which will count and print possible positions for n-digits.

Can you please say why you want to do this and why you think you need "recusive for loops"? I am pretty sure there is a simpler way to print the same sequence of numbers on the screen — 463035818_is_not_an_ai, Oct 29 '15 at 21:16
actually its not clear at all what you are asking. "not working as intended" what do you intend to do ? — 463035818_is_not_an_ai, Oct 29 '15 at 21:20
i corrected my post to be more exact and clear. I saw that i need new one new loop when i want to count one more digit in sentence, i may be wrong. — Sinma, Oct 29 '15 at 21:25
Oh hey! I recognize this problem! I've written a generic algorithm to solve it! http://ideone.com/HZkpW4 (next_increasing if they're unique, next_equal if duplicates are allowed) — Mooing Duck, Oct 29 '15 at 22:03
Suggested edit for problem statement: "for 3: 1, 2, 3, 12, 13" should be "for 3: 1, 2, 3, 12, 13, 23, 123". — rcgldr, Oct 30 '15 at 01:29

score 2 · Accepted Answer · answered Oct 29 '15 at 22:17

2

I did recursion to count possibility myself, but love you guys for all your help.

My recursion is

void col(int ilosc)
{
    static int st;
    for (int i = st++; i < k; i++)
    {
        if (ilosc > 1)
            col(ilosc - 1);
        else
            sposob++;
    }
}

where ilosc is digits number and sposob is count of possible positions numbers.

NOTE: sposob and k is global variables.

answered Oct 29 '15 at 22:17

Sinma

91
1
8

well, now this I dont really understand ;) but if it works, you should accept the answer – 463035818_is_not_an_ai Oct 29 '15 at 22:25

score 1 · Answer 2 · answered Oct 29 '15 at 21:44

1

I am not sure whether recursion is the best choice here, but you could do it like this:

typedef std::vector<int> IV;
IV getFirst(int k){
    IV res;
    for (int i=0;i<k-1;i++){res.push_back(i+1);}
    return res;
}

bool getNext(IV& numbers,int i){
    if (i==-1){return false;} // end of recursion
    if (numbers[i]>i+1){return getNext(numbers,i-1);}
    numbers[i]++;
    return true;
}
bool getNext(IV& numbers){  // start of recursion
    return getNext(numbers,numbers.size()-1);
}

int main() {
    IV numbers = getFirst(5);
    for (int i=0;i<numbers.size();i++){std::cout << numbers[i];}
    std::cout << std::endl;
    while(getNext(numbers)){
        for (int i=0;i<numbers.size();i++){std::cout << numbers[i];}
        std::cout << std::endl;
    }
}

answered Oct 29 '15 at 21:44

463035818_is_not_an_ai

109,796
11
89
185

that nice code, i need to look close at it, cuz i don't get it for 100%, and what would your suggestion for better choice? – Sinma Oct 29 '15 at 21:57
@Sinma I would try to replace the recursion by a loop, but actually there would not be much difference other than better readability (maybe) – 463035818_is_not_an_ai Oct 29 '15 at 22:04
thanks for your help, i did in that time myself recursion to count possible way, now its matter of time when i will do everything else. – Sinma Oct 29 '15 at 22:11

DeepDeadpool · Answer 3 · 2015-10-29T22:00:23.147

I think this will get you pretty close. I have an occasional repeat here, but this should set you on the right path.

const int max_depth = 5; // How long your string is
const int max_digit = 3; // Max digit you are counting to
int *nums = new int [max_depth];

void recurse_count(int depth)
{
    if (depth < max_depth)
    {
        for(int i = depth; i <= depth+1; i++)
        {
            nums[depth] = i;
            recurse_count(i+1);
        }
    }
    else
    {
        for (int j = 0; j < max_depth; j++)
            cout<<nums[j]+1;
        cout<<endl;
    }
}

int main()
{
    recurse_count(0);
    return 0;
}

score 0 · Answer 4 · answered Oct 29 '15 at 22:53

My approach (still too early in the evening probably, I had problems with it)

namespace detail
{
    void recurse_hlp(int min, int max, std::vector<int> vals, std::function<void(const std::vector<int>&)> f, std::size_t ptr)
    {
        if (ptr == vals.size())
            f(vals);
        else
        {
            for (int i = min; i <= max; ++i)
            {
                vals[ptr] = i;
                recurse_hlp(min, max, vals, f, ptr + 1);
            }
        }
    }
}

void recurse(int min, int max, int count, std::function<void(const std::vector<int>&)> f)
{
    std::vector<int> vals(count);
    detail::recurse_hlp(min, max, vals, f, 0);
}

void print(const std::vector<int>& vals)
{
    for (int v : vals)
        std::cout << v << " ";
    std::cout << std::endl;
}

int main()
{
    recurse(0, 5, 3, &print);
}

recurse gets a function accepting std::vector<int>, which contains all numbers from min to max up to count places.

Recursion of for's

4 Answers4

Linked