Calculating all possibilities

Hi,

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 :
             
             Columns
             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
etc......
almorrisAsked:
Who is Participating?
 
imladrisCommented:
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.
0
 
imladrisCommented:
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.
0
 
jkrCommented:
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 ;
    }
}

0
Cloud Class® Course: C++ 11 Fundamentals

This course will introduce you to C++ 11 and teach you about syntax fundamentals.

 
almorrisAuthor Commented:
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.

Thanks
Aaron
0
 
imladrisCommented:
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.
0
 
almorrisAuthor Commented:
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.
0
 
almorrisAuthor Commented:
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.

Thanks
Aaron
0
 
almorrisAuthor Commented:
Hi imladris,

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

Thanks
Aaron
0
 
DanRollinsCommented:
>> 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
0
 
ashooooCommented:
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).
0
 
ashooooCommented:
>> 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.

0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.