Thread: all possible combinations of an array

  1. #1
    Registered User
    Join Date
    Jan 2008
    Posts
    8

    all possible combinations of an array

    Hi,
    I have a small question about arrays. I have tried to find a way for getting all possible combinations of an array with just one dimension. I have spent some days to get the solution, without any progress. Could someone help me with my problem. Or at least help me on the way.

    Thanks in advance. And if its really really obvious sorry for this dumb question.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    What does "all possible combinations of an array" mean?

  3. #3
    Registered User
    Join Date
    Jan 2008
    Posts
    8
    if you have an array for instance 1,2,3,4 I want to have the program make the following combinations:

    1,2,3,4

    1+2 , 1+3 , 1+4

    1+2+3 , 1+2+4

    1+2+3+4

    2+3 , 2+4 ,etc.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    The way I like to think of this problem is the "odometer" method: Imagine an odometer in binary with four digits (one digit for each item in your array). So it would start as follows:
    0000
    0001
    0010
    0011
    0100
    0101
    0110
    0111
    etc.
    If the i'th digit is one, include that element, otherwise don't. So the first combination would be empty; the next would have just the fourth element; the next would have just the third, and so on. (Notice that this is the same way that you generate the rows of a truth table, for instance; it's the same problem.)

  5. #5
    Its hard... But im here swgh's Avatar
    Join Date
    Apr 2005
    Location
    England
    Posts
    1,688
    you mean somthing like:

    Code:
    int data[ 4 ] = { 1, 2, 3, 4 };
    
    std::cout << "Sum is: " << data[ 0 ] + data[ 1 ] + data[ 2 ] + data[ 3 ] << std::endl;
    I am only guessing here
    Double Helix STL

  6. #6
    Registered User
    Join Date
    Jan 2008
    Posts
    8
    thank you for your replies,
    tabstop your idea was great thank you. I tried to make a code that makes that binairy odometer, it works partly, because after the 5 digits it gives rubbish information. The problem is that he has to go up to 32000000 digits. Is it possible with this program structure, if not could someone tell me how it has to be done? thank you in advance.
    here is the code:
    Code:
    #include <iostream>
    #include <cmath>
    using namespace std;
    
    
    
    int main()
    {
        long getal;
        
        cin>>getal;
        double kopie=getal;
        long hoi=pow(2,kopie);
        
        cout<<hoi<<endl;
        bool tabel[getal][hoi];
        for(int n=0;n<=hoi;n++)
        {
            for(int t=0;t<=getal;t++)
            {
                tabel[t][n]=false;
            }
        }
        
        for(int n=0;n<=(hoi);n++)
        {
            if (n==0)
            {n++;}
            for(int t=0;t<=getal;t++)
            {
                tabel[t][n]=tabel[t][n-1];
            }
            for(int ok=0, h=0;ok==0;)
            {
                if (tabel[h][n]==false)
                {tabel[h][n]=true;ok=1;}
                else
                {
                    tabel[h][n]=false;
                    h++;
                }
            }
        }
        
        for(int n=0;n<=hoi;n++)
        {
            for(int t=0;t<=(getal-1);t++)
            {
                if(tabel[t][n]==true)
                {cout<<1;}
                else
                {cout<<0;}
            }
            cout<<endl;
        }
        char stop;
        cin>>stop;
        return(0);
    }
    sorry for the big main but I am not that good in programming and I hadn't that much time to put everything in functions
    Last edited by hoppy; 01-10-2008 at 04:13 PM.

  7. #7
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Even if you try with 5 items, you get some things printed out, but they don't make sense. I don't quite follow what your loop is trying to do?

  8. #8
    Registered User
    Join Date
    Jan 2008
    Posts
    8
    the first loop is filling the array with false,
    the second loop makes the odometer,
    and the third loop translates the bool chars to 1 and 0

    here the program works up to 5 items after 5 I get rubbish.

    for the second loop:
    first he looks to the last made row of digits and copies it.
    then he put true on the first spot, if there's already true he changes this true in false and goes to the next spot. etc.

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    A hint is that the binary "odometer" is just a number being incremented by one. It probably won't be very efficient - but I guess efficiency is not the concern here - but you might just use an integer and check which bits are set. std::bitset might be handy for that.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  10. #10
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Your bounds checks are off; you should change <= to < almost everywhere (remember: a 5-element array only has elements through a[4]).

  11. #11
    Registered User
    Join Date
    Jan 2008
    Posts
    8
    thnx tabstop I'll look if I can make something with this

  12. #12
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    32000000 digits? 32000000 elements in the array you want all combinations of?

    Well, if you ever get your program working, I'll see you next decade.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 16
    Last Post: 05-29-2009, 07:25 PM
  2. from 2D array to 1D array
    By cfdprogrammer in forum C Programming
    Replies: 17
    Last Post: 03-24-2009, 10:33 AM
  3. Replies: 6
    Last Post: 11-09-2006, 03:28 AM
  4. Unknown Memory Leak in Init() Function
    By CodeHacker in forum Windows Programming
    Replies: 3
    Last Post: 07-09-2004, 09:54 AM
  5. Quick question about SIGSEGV
    By Cikotic in forum C Programming
    Replies: 30
    Last Post: 07-01-2004, 07:48 PM