Go Premium for a chance to win a PS4. Enter to Win


Calculating all possibilities

Posted on 2003-11-24
Medium Priority
Last Modified: 2010-04-01

I want to make a lookup table that holds every combination of  (31 chars) within a (100 chars)(3100 posibilities). For Example this is what the first few values may look like :
             1   | 2   | 3   | 4   | 5   ........................... 100
Values    1     1      1     1     1  .............................. 1
Values    1     2      1     1     1  .............................. 1
Values    1     1     2      1     1  .............................. 1
Values    1     1      1     2     1  .............................. 1
Values    1     1      1     1    2   .............................. 1
Values    1     1      1     1    1   .............................. 2
Values    1     3      1     1     1  .............................. 1
Question by:almorris
  • 4
  • 3
  • 2
  • +2
LVL 16

Expert Comment

ID: 9813656
Actually, the total number of possibilities would be 31^100 (31 to the power 100). That is a number with more than 100 zeroes. A lookup table in any form would either be impractical or impossible.

Perhaps an explanation of what you want this *for* might enable us to help you in some other way.
LVL 86

Expert Comment

ID: 9813675
This problem seems to be perfect for 'std::next_permutation()', e.g.

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

using namespace std ;

void main()
    const int VECTOR_SIZE = 3 ;

    // Define a template class vector of strings
    typedef vector<string> StrVector ;

    //Define an iterator for template class vector of strings
    typedef StrVector::iterator StrVectorIt ;

    //Define an ostream iterator for strings
    typedef ostream_iterator<string> StrOstreamIt;

    StrVector Pattern(VECTOR_SIZE) ;

    StrVectorIt start, end, it ;

    StrOstreamIt outIt(cout, " ") ;

    start = Pattern.begin() ;   // location of first
                                      // element of Pattern

    end = Pattern.end() ;       // one past the location last
                                       // element of Pattern

    //Initialize vector Pattern
    Pattern[0] = "A" ;
    Pattern[1] = "B" ;
    Pattern[2] = "C" ;

    // print content of Pattern
    cout << "Before calling next_permutation...\n" << "Pattern: " ;
    for(it = start; it != end; it++)
        cout << *it << " " ;
    cout << "\n\n" ;

    // Generate all possible permutations

    cout << "After calling next_permutation...." << endl ;
    while ( next_permutation(start, end) )
        copy(start, end, outIt) ;
        cout << endl ;


Author Comment

ID: 9813767
Hi imladris,

I want to write a dictionary based encoder for encoding a picture.  The picture currently is 100px x 100px and each pixel value can be 1 to 31. although the max value is 31 I still need to use a UChar to store each pixel. giving me a size of 10000bytes.  I want to cut this size down by representing each row with a int number that in a lookup table gives me the 100px pattern, so instead of using 100 UChars to store a row I store 1 int value that can retrieve to pattern.

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

LVL 16

Expert Comment

ID: 9814051
10000 bytes, which is 10K hardly seems like an exorbitant outlay on todays machinery which comes with a minimum of Megabytes of RAM, and Gigabytes of harddisk space.

If the resources taken are not significant, it is often better to stick with the simple algorithm.

In addition, in this case, the size of the lookup table would far outstrip the size of storing the image, even if you take a UChar per pixel.

There are probably ways of cutting down the 10K of storage for them. It looks like theoretically the storage should be able to be reduced to 6250 bytes (10000 pixels of 5 bits = 50000 bits and 50000 / 8 = 6250 bytes). Though again, at the cost of increased complexity of your code. Unless you are storing many hundreds of such images, I doubt the tradeoff would be worthwhile.

Author Comment

ID: 9814219
Hi imladris,

i plan to use the pictures to create a small video confrencing app.  and the 10,000bytes will probably be at 15fps about 146k of data (not good for dialup).  This is why building a lookup would be better, instead of 146k per second it could be cut down to (2 * 100) * 15 about 2K.

Author Comment

ID: 9814328
hi  jkr,

Thanks for the example, I'm not too hot with the Standard Lib suff.  I'll work through it and let you know how it goes.

LVL 16

Accepted Solution

imladris earned 1500 total points
ID: 9814529
Unfortunately Aaron, the harddrive to hold your lookup table hasn't been invented yet.

According to your estimate 31 chars over 100 positions is 3100 possibilities. Let's test that shall we. If we take a smaller case, say 3 characaters over 3 positions, you would say the size of the lookup table is 9 (3 * 3), right?

Well here are the permutations:

 1 1 1
 1 1 2
 1 1 3
 1 2 1
 1 2 2
 1 2 3
 1 3 1
 1 3 2
 1 3 3
 2 1 1
 2 1 2
 2 1 3
 2 2 1
 2 2 2
 2 2 3
 2 3 1
 2 3 2
 2 3 3
 3 1 1
 3 1 2
 3 1 3
 3 2 1
 3 2 2
 3 2 3
 3 3 1
 3 3 2
 3 3 3

That is, as you can see, there are 27 permutations. Not 9. The total possibilities are represented by 3 * 3 * 3, i.e. 3 ^ 3. The number of characters to the power of the number of positions. For 31 characters over 100 positions that is an unimaginably large number.

You're right that you need to do something to squeeze that frame rate through a phone wire. But a lookup table isn't going to do it for you.

The tactic that is generally used for such things is based on the observation that one video frame is usually very similar to the next. Calculating and transmitting some kind of "difference" and using that to update the frame is something that can be squeezed through the wire. Doing the difference calculation fast enough becomes the new trick.

Author Comment

ID: 9814657
Hi imladris,

Thanks for your help on this.  I guess 31^100 is even too big for my calculator. :)

LVL 49

Expert Comment

ID: 9816874
>> I want to cut this size down by representing each row with a int number that in a lookup table gives me the 100px pattern.

Watch me pull a rabit out of my hat!  You can't pack more data than will fit.  The lookup key would be as large as the value itself!

What you need to do is use a compression scheme, such as huffman encoding or LZ.  The easiest way to do that is use a standard PKZIP library to compress on one end and decompress on the other.  The time involved is insignificant compared to the treansmission time.  You are probably talking about grayscale and images which will compress quite well -- I'd guess about 50%.

Another idea is to sacrifice quality -- a "lossy" compression algorthytm.  Make the 100x100 image into a 25x25 image before sending and expand it back before displaying (four times as fast).  Or cut the number of shades down to 15 instead of 31.  That will make the images half the size, so twice as fast to transmit.

The next idea is to write code that compares each image to the previous one, then transmit specially-formatted packets that just describe the differences.  That will provide a tremendous boost... Think of a person talking... usually only his mouth moves so you might only need to senfd about 200 pixels worth of data rather than 10,000.  This method is, in fact, the way most streaming video works.

-- Dan

Expert Comment

ID: 9818311
Hi Aaron, converting each permutation to an integral value will NOT compress your image for sure.
The reason is... there are 30^100 permutations of 1's and 2's. So, the number of permutations are 1.3682623708966451600678492270201e+149. Doing simple log calculations... i.e.

log(1.3682623708966451600678492270201e+149)/log(2) = 495.41963103868752088061235991756

Therefore 1.3682623708966451600678492270201e+149 = 2^495.41963103868752088061235991756

That means you will need 496 bits to store one value. Thats 62 bytes approxiamately. Whereas without all this mess you just needed 100 bits to store 100 values. Now you need 496 bits to store ONE value.

I dont think its a very nice idea. And besides, the time needed to compute one permutation that is, say, midway in the sequence would take a few years (I may be wrong here).

Expert Comment

ID: 9818439
>> That means you will need 496 bits to store one value. Thats 62 bytes approxiamately. Whereas without all this mess
>> you just needed 100 bits to store 100 values. Now you need 496 bits to store ONE value.

Sorry, I meant, without all this mess you just needed 100*31 bits to store 100 values, ie. 31 (or 32) bits to store one value. Now you need 496.


Featured Post

Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
Suggested Courses

772 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question