0

I have been looking for a language and code to help me calculate all possible subsets of a set of 3600 elements. At first my search started with python, then I went through JavaScript and then came to Perl. I know using Perl to calculate all subsets as shown in https://rosettacode.org/wiki/Power_set having 16GB of ram there is a significant memory consumption, but I'm not sure if anything better than perl or this script bellow:

MY MWE:

use ntheory "forcomb";
my @S = qw/1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30/;
forcomb { print "[@S[@_]]  " } scalar(@S);
print "\n";
7beggars_nnnnm
  • 697
  • 3
  • 12

3 Answers3

1

There is no calculator that can handle so much elements in memory.

The number of possible subset starting from a set of 3600 elements is 2^3600.

This number is very big. Consider that

2^10 is close to 1.000
2^20 is close to 1.000.000
2^30 is close to 1.000.000.000

Basically every 10 you add three zeros, so with 2^3600 you have a number with 1200 zeros of different combinations, which is an unimaginable big number.

You can't solve this problem also saving the data to disk and using all the existing computers on the earth.

With all the computers existing on the earth (a number close to 2.000.000.000, so 2^31 computers) and imagine a disk space of a terabyte for each of them (2^40 bytes) you can imagine storing information for a set of 71 elements (71 not 3600) using a single byte to store each number and without considering the extra space to store the set information... take your consideration based on that.

You can eventually imagine giving a sort order to all the possible subsets and coding an algorithm that gives you the nth subset based on that sort. This can be done because you don't need to calculate and store all possible subsets, but calculate just one using some rule. If you are interested we can try to evaluate such solution

Davide Lorenzo MARINO
  • 26,420
  • 4
  • 39
  • 56
0

For a set s (with size |s|), the size of its power set P(s) is |P(s)| = 2^|s|.

Never-mind the memory. You'd need 2^3600 iterations to calculate each value.

This is totally computationally intractable in this universe.

Alexander
  • 59,041
  • 12
  • 98
  • 151
  • I am not sure https://stackoverflow.com/a/8535241/10824251 – 7beggars_nnnnm Aug 11 '21 at 01:43
  • @7beggars_nnnnm Yes, there are lazy enumerators that can generate the values on-demand, but that's missing the point. `2^3600` is roughly `10^1083`. [The number of particles in the universe is estimated to be on the order of `10^80`](https://www.popularmechanics.com/space/a27259/how-many-particles-are-in-the-entire-universe/). What you're trying to do is calculate a number of elements which is `10^1003` ***times*** more than that. – Alexander Aug 11 '21 at 01:46
0

Take Java (or another compiled language like Pascal with some bit support).

It has BitSet, so 3600 elements are represented with approximately 3600/8 = 450 bytes. All possibilities would be 23600: to much to iterate. One could iterate with a BigInteger, every ith bit representing an element.

Simple iterating with a BigInteger upto 23600 - 1 should make it your (descendants') life's work. Be aware that this kind of problem is something for quantum computing.

But I assume you have a very smart algorithm pruning most possibilities.

It would be nice to have dependencies like in sudoku. Then maybe a logic language or some rule engine might do.

Should 3600 be the seconds in an hour which you have to combine, please consider spending that hour otherwise.

Joop Eggen
  • 107,315
  • 7
  • 83
  • 138