combinations

[something]

I have a problem for generating combinations for entered ammount of numbers.
for example without getting the entered ammount the loop would look like

for (int n=1; n<=3; n++)
    {
      for (int x=1; x<=3; x++)
         {
          for (int y=1; y<=3; y++)
           {
             cout << n << x << y << endl;
           }
         }
    }

But how do i do this for entered ammount of numbers? The length of the output string should be the same as the entered ammount.

Sorry. I'm bad at explaining stuff.

[R0mai]

Maybe
http://cplusplus.com/reference/algorithm/next_permutation/

[m4ster r0shi]

That's permutations, he doesn't want that. He doesn't want combinations either. As you can see from his code, he wants every digit to be able to get every possible value, regardless of the values of the other digits (meaning that repetition is allowed).

#include <iostream>
#include <vector>
using namespace std;

ostream & print(const vector<int> & v)
{
    int size=v.size();
    for (int i=0; i<size; i++)
        cout << v[i] << ' ';
    return cout;
}

int main()
{
    int digit_count;
    int digit_values;

    cout << "enter number of digits (>0): ";
    cin >> digit_count;

    cout << "enter number of digit values (>0): ";
    cin >> digit_values;

    vector<int> vint;
    vint.resize(digit_count);

    for (int i=0; i<digit_count; i++)
        vint[i]=0;

    print(vint) << endl; //lol

    int carry;

    while (true)
    {
        carry=1;

        for (int i=0; i<digit_count; i++)
        {
            int & cur=vint[i];

            cur+=carry;
            if (cur==digit_values)
            {
                cur=0;
                carry=1;
            }
            else
            {
                carry=0;
                break;
            }
        }

        if (carry==1) break;

        print(vint) << endl;
    }

    return 0;
}

[jsmith]

Hey m4ster r0shi... try out this:

#include <boost/lambda/lambda.hpp>
#include <algorithm>
#include <vector>

std::vector<int> v;
std::for_each( v.begin(), v.end(),
    std::cout << "The numbers are: " << boost::lambda::_1 << ' ' );

[m4ster r0shi]

Please, stop it... I don't want to see boost code in my sleep tonight...

[Albatross]

Someone I see doesn't like boost, which I think is an excellent library. Notice: 7 lines vs 61.
Oops.

-Albatross

12*10^2 posts, and counting.

[m4ster r0shi]

Albatross wrote:

Notice: 7 lines vs 61.

I think you missed something here... He proposed a replacement for the print function, not the whole code...

[Duthomhas]

That's permutations, he doesn't want that. He doesn't want combinations either. As you can see from his code, he wants every digit to be able to get every possible value, regardless of the values of the other digits (meaning that repetition is allowed).

That's a permutation where repetition is permitted.
http://www.mathsisfun.com/combinatorics/combinations-permutations.html

@something
The counting numbers are the same thing as what you are asking. Think for a second about this:

  00      05      10      15      20  
  01      06      11      16      21
  02      07      12      17      .
  03      08      13      18      .
  04      09      14      19      .

The only thing you must be aware of is your set of 'digits'. For ordinary counting, we use the digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9.

In computing, we often use different sets. For example, the octal set contains only the digits 0, 1, 2, 3, 4, 5, 6, and 7 -- eight digits total. If I try to add one to 07, I get 10. That is, the digit in the rightmost place starts over with the first and the one on the left is incremented to the next digit. (It too may roll over.)

This roll-over and increment the next to the left is called a carry.

While m4ster r0shi gave you code to do this kind of thing, you really should spend time trying to figure it out yourself. Understanding what is going on will help you significantly later on when you are doing more interesting things.

Hope this helps.

[m4ster r0shi]

Duoas wrote:

That's a permutation where repetition is permitted.

Oh, ok. I'm from Greece and we use different terms here. When you have to put n (distinct) objects in n places, caring about the order and without repetition allowed, we call it a permutation of n objects. That is, a permutation by definition prohibits repetition.

A permutation is a special case of something that I couldn't find the english term for :/ When you have to put n (distinct) objects in k (<=n) places, caring about the order, we call it, let's say "ordering" (I don't know the english term). An "ordering" can be "repetitive" (i.e. repetition is allowed) or not. A permutation is a non-"repetitive" "ordering" where k==n.

What I wrote for the OP was the "repetitive" "ordering" of n objects in k places, where n==digit_values and k==digit_count. This, by definition, in my language, is not a permutation (not even if k==n, because it's still "repetitive").

We use the term "permutations with repetition" to describe the following situation:

You have n (non-distinct) objects, where k1 of them are identical to each other, k2 of them are identical to each other, ... and k1+k2+...==n (obviously) and you want to put them in n places, caring about the order of the non-identical objects. The number of ways you can do this is n!/(k1! * k2! * ...).

EDIT: Mmmm... Take a look at this-> http://mathworld.wolfram.com/Permutation.html
It defines permutations the way I do. I guess then that your site just oversimplifies things because it's a site for kids.

[moorecm]

jsmith wrote:

#include <boost/lambda/lambda.hpp>
#include <algorithm>
#include <vector>

std::vector<int> v;
std::for_each( v.begin(), v.end(),
    std::cout << "The numbers are: " << boost::lambda::_1 << ' ' );

I like boost and all but when you don't need it... :P

#include <algorithm>
#include <iterator>
#include <vector>

std::vector<int> v;
std::copy( v.begin(), v.end(), std::ostream_iterator<int>( std::cout, " " ) );

[firedraco]

std::ostream_iterator<int>

Wow, I didn't even know that existed...you learn something new every day I guess.

[jsmith]

That's true. Thing is, for some reason I can never remember the ostream_iterator way off the top
of my head, but I can remember the lambda way :)

[m4ster r0shi]

The reason is that you are a boost addict :D

[jsmith]

Ok, so here's m4ster r0shi's 61-line program in 23 lines with only
two real lines of logic:

#include <iostream>
#include <string>

void do_it( std::string s, size_t digits_left, size_t max_values ) {
    if( digits_left )
        for( size_t digit = 0; digit < max_values; ++digit )
            do_it( s + static_cast<char>( digit + '0' ), digits_left - 1,
                max_values );
    else
        std::cout << s << std::endl;
}

int main() {
    size_t max_length, max_values;

    std::cout << "enter number of digits (>0): ";
    std::cin >> max_length;

    std::cout << "enter number of digit values (>0): ";
    std::cin >> max_values;

    do_it( "", max_length, max_values );
}

[m4ster r0shi]

Nice... I see you didn't use boost at all... GJ boost-boy! :D