Arrays - Storing millions of numbers.

[kyiro37]

I am trying to write a program that will generate over 100 million different number combinations. I have 6 arrays that I need to be able to hold over 100 million numbers each. I am only a beginner so I don't know of another way to do this without arrays and whatever.

My question is: I understand trying to store that many numbers in RAM (arrays are put into RAM, right?) isn't going to work. How do I get around this?

Thank you.

[giblit]

You can make a class object. Or maybe store the numbers into strings. Also might I suggest a vector if the number is a random number and you do not know it before hand?

[mik2718]

start off by calculating exactly how much RAM you need.

an int (32bit) is 4 bytes, a float is 4 bytes and a double is 8 bytes

If this is less than the RAM you have (minus some stuff for operating system etc) then you are OK

otherwise you have to;

think - do I really need to store this many numbers, can they be generated algorithmicly? Modern processors are fast, so even if the calculations are complex they may fit into the time available.

store some on disc - note that this will be slow and possibly you might want to just rely on the OSes swap system, but if you are storing some on disc then you can think about how to organise your program to minimise disc access

or, buy more RAM

[Duthomhas]

Don't use straight arrays. Use a std::deque. Memory requirements are more flexible that way.

Hope this helps.

[kyiro37]

Well what I am trying to do is make over 100 million number combinations at random, but I need to be sure I don't make any duplicates. I'm sure there's an easier way to do it than randomizing it, but I am still new to this.

I thought of using arrays so I could make sure there were no duplicates. But I realize checking it like that wastes time/processing power.

I basically just want to make a list that has over 100 million number combinations (9 numbers) -- every combination possible. But I want it to be in a random order.

[Duthomhas]

This is honestly a valid question to help answer your problem:

What exactly are you going to do with all those numbers?
(That is, where do you put them once you generate them?)

[giblit]

What I would do is use a vector or deque like duoas said since he probably knows better but I haven't used one before but when I read up on it, it sounded almost identical. Then use generate with the next_permutation algorithms. That will ensure you have no matching "combinations" which is technically called permutations if they had matching it would be called a combination but you don't want them matching.
http://www.mathsisfun.com/combinatorics/combinations-permutations.html

Say for example you have the numbers 112.
The combinations for that would be
112.
112.
121.
121.
211.
211.
And the permutations would be
112.
121.
211.
http://www.cplusplus.com/reference/algorithm/

[kyiro37]

Thank you everyone.

And Duoas, I just need to put them into a text file.

[TheIdeasMan]

Duoas's last post goes directly to the problem I think.

IMO using a vector with millions of data is a bad idea, because it is very inefficient due to having to reallocate memory, despite the capacity strategy.

You might need a combination of types of containers. A vector might be fine for storing a combination or permutation of a limited size, but have a different one for storing all of them a std::set or std::map and others come to mind, but which which one depends on what you want to do exactly.

I have a question:

Is this for one of the on-line problem solving questions?

If so, then I would say that the solutions are not as trivial as they may seem. For example they limit the run time to 1 second, but a naive approach means processing factorial n combinations, which for a number that is larger than an unsigned 64 bit quantity might take your computer more than a minute to process. So you need to implement a smart algorithm that cuts down on unnecessary processing.

giblit wrote:

What I would do is use a vector or deque like duoas said since he probably knows better but I haven't used one before but when I read up on it, it sounded almost identical.

There are differences in the way various containers are implemented. For example, try to find out the differences between array, std::array, vector, list, set, map etc.

HTH

[kyiro37]

Okay. Well I only know very basic things right now, but this is exactly what I want to do:

I want to output every possible permutation of numbers 1-50 6 times.

So:

1 1 1 1 1 1
1 1 1 1 1 2
...
45 45 45 45 45 45
45 45 45 45 45 46


etc..

I just want to output to a text file. (excel would be nice but I don't know how to do that yet either.)

I originally wanted to just randomize it to find all possible combinations but that is not necessary. The list can be randomized after it is made.

Any pointers?

Thank you!

[JLBorges]

> I want to output every possible permutation of numbers 1-50 6 times.

#include <iostream>
#include <vector>

void generate_all_random_permutations( int min, int max, std::size_t length,
                                       std::ostream& stm,
                                       std::vector<int> generated_so_far = {}  )
{
    if( length == 0 )
    {
        for( int v : generated_so_far ) stm << v ;
        stm << '\n' ;
    }
    else
    {
        for( int v = min ; v <= max ; ++v )
        {
           generated_so_far.push_back(v) ;
           generate_all_random_permutations( min, max, length-1, stm, generated_so_far ) ;
           generated_so_far.pop_back() ;
        }
    }
}

int main()
{
    generate_all_random_permutations( 1, 3, 4, std::cout ) ;
}

http://ideone.com/bOKRA1


For an elegant solution to the original problem, see: http://www.cs.ucdavis.edu/~rogaway/papers/subset.pdf

For more information: http://scholar.google.com/scholar?q=Format-preserving+encryption