How do I make a *HUGE* array in C++?

Hi, I'm trying to work out the permutations of 6 numbers in 3 columns, long story short it works out to 720*720*720 permutations, or 373248000 columns by 18 rows. Is there some way to declare an array of this size or is there another way I should be looking at this problem? Any help will be much appreciated.

I know that but I don't need to store one number of 373248000, i need to store 373248000 values in an array. Which makes an array of around 38 megabytes, which makes your value of 1844674407360955161, which is 6 bytes, look puny by comparison.

You should probably try to look at it another way. 6 billion values, even if they were only a byte each, is still more memory than people have on their machines. Each row is over 300 megabytes.

Do you really need all values to be available at once? Can you use lazy evaluation to only compute and store the values you need? Perhaps you only ever need one chunk of columns at a time. If you need all the values available because it is expensive to recompute them, perhaps you can store the computed data in a file or files for lookup later. What types of values are your storing? If the range of numbers is small, you could use bit manipulation to combine the values to reduce the amount of memory you need.

There are plenty of options, depending on the details of your circumstances.

I know that but I don't need to store one number of 373248000, i need to store 373248000 values in an array.

Yes, I know. I thought an array subscript could be an unsigned long, but when I tried it on my computer I got an error about the subscript being too big. I got the same error for an int which is only roughly 2 billion--even though the first time I tried it, it worked.

Are you sure about the figures? 6 numbers taken 3 at a time gives me 120(6*5*4) permutations and if I allow reuse of numbers at most 216 (6*6*6)..maybe you stated something wrong or left out a detail

Do you actually need to store the values or just use them? You can use std::next_permutation() to generate them as needed.

You can also generate them to a file.

Originally Posted by Daved

You should probably try to look at it another way. 6 billion values, even if they were only a byte each, is still more memory than people have on their machines. Each row is over 300 megabytes.

Do you really need all values to be available at once? Can you use lazy evaluation to only compute and store the values you need? Perhaps you only ever need one chunk of columns at a time. If you need all the values available because it is expensive to recompute them, perhaps you can store the computed data in a file or files for lookup later. What types of values are your storing? If the range of numbers is small, you could use bit manipulation to combine the values to reduce the amount of memory you need.

There are plenty of options, depending on the details of your circumstances.

Speed is essential for this program, but I could store the data to the drive, and since no value will be higher than 6, I'd only need one bit per value. I'm not to familiar with bit manipulation (Its been a while since assembly language where I learned that stuff) but I feel it may reduce the speed and I need a maximum look up time of 25 seconds. The reason I want to use an array is because of the enormous amount of data I need, which makes pointers impossible, otherwise I'd just do a sequential set of numbers but that would run the risk of writing over something important. I have enough RAM that I should have no problems running this, but I just need to find a way to store it all. I might be just pipe dreaming thinking this will work at all, but I was hoping a more experienced programmer would have heard of something like this and be able to help.

Originally Posted by Darryl

Are you sure about the figures? 6 numbers taken 3 at a time gives me 120(6*5*4) permutations and if I allow reuse of numbers at most 216 (6*6*6)..maybe you stated something wrong or left out a detail

Do you actually need to store the values or just use them? You can use std::next_permutation() to generate them as needed.

You can also generate them to a file. Though it will end up being about 6 gig I imagine

Its 3 sets of 6 numbers, 1 to 6, or 720 permutations per set, or 720 cubed possible permutations. I will have to look into that std::next_permutation() , I've never heard of it and it may be exactly what I need. I'm really just worried that with this many values a look up table might be necessary for the speeds I need it to run at, but I'll give it a go. Thanks.

for a value of 6 you'd need 3 bits 110=6

Think we could see some code used to generate this list?

You only need one int to store a value from 1 to 720 that represents one of the 720 possible permutations. You need only 3 ints to indicate the values to be held in the columns for each row, and only 54 ints to indicate which permutations are held in the entire structure. You don't need to hold all possibilities, just the ones you are using. You could put the 720 permutations into an array, then have your 18 x 3 structure hold an index into that array for each location.

Code:

#include <iostream>
#include <deque>
#include <string>
#include <algorithm>

std::deque<std::string> aset;
unsigned lookup(std::string in)
{
	for (unsigned i = 0; i < 720; i++)
		if (aset[i] == in) return i;
}

void printPermutation(int x, int y, int z)
{
	std::cout << aset[x] << "," << aset[y] << ","<< aset[z] << std::endl;
}
void printPermutation(unsigned ordinal)
{
	int x,y,z;
	x= ordinal/518400;
	ordinal-=(x*518400);
	y = ordinal/720;
	ordinal-=(y*720);
	z = ordinal;
	printPermutation(x,y,ordinal);
}
void printXYZ(std::string a, std::string b, std::string c)
{	
	std::cout << lookup(a) << "," << lookup(b) << ","<< lookup(c) << std::endl;
}

void printOrdinal(std::string a, std::string b, std::string c)
{	
	std::cout << lookup(a)*518400+ lookup(b)*720+lookup(c) << std::endl;
}
int main()
{
	std::string val = "123456";
	aset.push_back(val);
	while(std::next_permutation(val.begin(),val.end()))	aset.push_back(val);
	std::cout << aset.size() << std::endl ; //just to show it create 720 permutations
	printPermutation(3, 10, 650);
	printPermutation(3057652);
	printXYZ("156423","354216","615342");
	printOrdinal("156423","354216","615342");
}

My version:

Code:

#include <iostream>
#include <istream>
#include <ostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <limits>
#include <cstdlib>
#include <ctime>

typedef std::vector<int> data_set;
typedef std::vector<data_set> data_row;
typedef std::vector<data_row> data_table;

void output_set(const data_set& out_set)
{
    std::copy(out_set.begin(), out_set.end(), std::ostream_iterator<int>(std::cout, ","));
}

void output_row(const data_row& out_row)
{
    std::cout << "|  ";
    for (data_row::const_iterator iter = out_row.begin(),
        end = out_row.end(); iter != end; ++iter)
    {
        output_set(*iter);
        std::cout << "  |  ";
    }
}

void output_table(const data_table& out_table)
{
    for (data_table::const_iterator iter = out_table.begin(),
        end = out_table.end(); iter != end; ++iter)
    {
        output_row(*iter);
        std::cout << std::endl;
    }
}

int get_next_index(unsigned int num_choices)
{
    static bool use_rand = false;
    if (!use_rand)
    {
        unsigned int index = num_choices;
        std::cout << "Pick a permutation (0-" << num_choices-1;
        std::cout << "), enter " << num_choices << " to pick randomly: ";
        while ((!(std::cin >> index)) || std::cin.peek() != '\n' || index > num_choices)
        {
            std::cin.clear();
            std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
            std::cout << "Invalid permutation index. Pick a permutation (0-";
            std::cout << num_choices-1 << ") or " << num_choices << ": ";
        }
        std::cin.ignore();

        if (index == num_choices)
        {
            use_rand = true;
            srand(static_cast<unsigned>(time(0)));
        }
        else
        {
            return index;
        }
    }
    return rand() % num_choices;
}

int main()
{
    int base_set[] = { 1, 2, 3, 4, 5, 6 };
    const int num_n = (sizeof(base_set)/sizeof(base_set[0]));
    const int num_cols = 3;
    const int num_rows = 18;

    std::vector<data_set> permutations(1, std::vector<int>(base_set, base_set+num_n));
    while (std::next_permutation(base_set, base_set+num_n))
        permutations.push_back(std::vector<int>(base_set, base_set+num_n));

    const std::vector<data_set>::size_type num_permutations = permutations.size();

    data_table data(num_rows, data_row(num_cols, data_set(num_n)));
    for (int row_index = 0; row_index < num_rows; ++row_index)
        for (int col_index = 0; col_index < num_cols; ++col_index)
            data[row_index][col_index] = permutations.at(get_next_index(num_permutations));

    output_table(data);
}