Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17


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
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 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.

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

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

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
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…
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 be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

670 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