Programming Forums - Newbie prob:how to make combinations without repeatition

Programming Forums (http://www.programmingforums.org/forumindex.php)

- C++ (http://www.programmingforums.org/forum15.html)

- - Newbie prob:how to make combinations without repeatition (http://www.programmingforums.org/showthread.php?t=11059)

veiga2

Aug 13th, 2006 5:27 AM

Newbie prob:how to make combinations without repeatition

About the code in making the numbers from 1-42, in different combinations without repeatition, by 6 numbers, is there any function about that?, hmmmm... i cant find the answer on this... i know im going to use the for loop but i cant find the solution... pls help me hnx

example: collection of numbers from 1-7
answer:
123456
123457
123467
123567
124567
134567
234567

Thanks for helping a newbie prob

grumpy

Aug 13th, 2006 8:35 AM

Use nested for loops, where the start or end conditions of inner loops are determined by the value controlling outer loops.

bl00dninja

Aug 15th, 2006 6:31 PM

uh, what the hell are you trying to do? "making numbers"? w/o repitition there is the fundamental theorem of arithmetic, which might help you.

uman	Aug 16th, 2006 1:41 AM

Next time, post in the proper forum: "Software design and algorithms".

std::vector<std::vector<value> >

get_combinations(std::vector<value> values, unsigned m)

{

        std::vector<std::vector<value> > ret;

        unsigned n = values.size();

        std::vector<value>::const_iterator* iters = 

                new std::vector<value>::const_iterator[m];

        for(unsigned i=0;i<m;i++)

                iters[i] = values.begin() + i;

        while(true)

        {

                unsigned i;

                std::vector<value> tmp;

                for(unsigned j=0;j<m;j++)

                        tmp.push_back(*(iters[j]));

                ret.push_back(tmp);

                

                for(i=m;i>0;i--)

                {

                        if(++(iters[i-1]) != values.end() - (m - i))

                                break;

                }

                if(!i)

                        break;

                for(unsigned j = i;j<m;j++)

                {

                        iters[j] = iters[j-1]+1;

                }

        }

        return ret;

}

It was hard work forcing my brain to solve this in a non-recursive way.

uman	Aug 16th, 2006 5:02 AM

By the way, that will use ten metric fucktons of memory if you run it with a lot of values. If you needed to find all the combinations of a large set of values, but you didn't need to hold them all in memory at once, it'd be far better to implement as find_first_combination() and find_next_combination() functions.

All times are GMT -5. The time now is 10:07 AM.