Solved

Calculating all possibilities

Posted on 2003-11-24
11
306 Views
Last Modified: 2010-04-01
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......
0
Comment
Question by:almorris
  • 4
  • 3
  • 2
  • +2
11 Comments
 
LVL 16

Expert Comment

by:imladris
Comment Utility
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
 
LVL 86

Expert Comment

by:jkr
Comment Utility
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
 

Author Comment

by:almorris
Comment Utility
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
 
LVL 16

Expert Comment

by:imladris
Comment Utility
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
 

Author Comment

by:almorris
Comment Utility
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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 

Author Comment

by:almorris
Comment Utility
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
 
LVL 16

Accepted Solution

by:
imladris earned 500 total points
Comment Utility
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
 

Author Comment

by:almorris
Comment Utility
Hi imladris,

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

Thanks
Aaron
0
 
LVL 49

Expert Comment

by:DanRollins
Comment Utility
>> 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
 
LVL 3

Expert Comment

by:ashoooo
Comment Utility
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
 
LVL 3

Expert Comment

by:ashoooo
Comment Utility
>> 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

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

762 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

Need Help in Real-Time?

Connect with top rated Experts

7 Experts available now in Live!

Get 1:1 Help Now