how to make a matrix with all combinations of digits efficiently

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

how to make a matrix with all combinations of digits efficiently

jeandubois
I'd like to generate a matrix like this (small version to give you the idea):

0 0 0 (three columns in this example)
0 0 1
0 0 2
0 0 3
.
.
.
9 9 8
9 9 9

Could anyone here show me how to do this efficiently?

thanks in advance

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: how to make a matrix with all combinations of digits efficiently

Juan Pablo Carbajal-2
On Thu, Dec 28, 2017 at 9:25 PM, Jean Dubois <[hidden email]> wrote:

> I'd like to generate a matrix like this (small version to give you the idea):
>
> 0 0 0 (three columns in this example)
> 0 0 1
> 0 0 2
> 0 0 3
> .
> .
> .
> 9 9 8
> 9 9 9
>
> Could anyone here show me how to do this efficiently?
>
> thanks in advance
>
> _______________________________________________
> Help-octave mailing list
> [hidden email]
> https://lists.gnu.org/mailman/listinfo/help-octave

This is the decomposition on base 10, a way of doing it is

nc         = 3; # number of columns
base     = 10;
i            = (0:(base^nc-1)).'; # row index - 1
counter = mod( floor (i ./ base.^[(nc-1):-1:0]), base);

it should work for any integer base, but please do check.

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: how to make a matrix with all combinations of digits efficiently

jeandubois
2017-12-29 0:07 GMT+01:00 Juan Pablo Carbajal <[hidden email]>:

> On Thu, Dec 28, 2017 at 9:25 PM, Jean Dubois <[hidden email]> wrote:
>> I'd like to generate a matrix like this (small version to give you the idea):
>>
>> 0 0 0 (three columns in this example)
>> 0 0 1
>> 0 0 2
>> 0 0 3
>> .
>> .
>> .
>> 9 9 8
>> 9 9 9
>>
>> Could anyone here show me how to do this efficiently?
>>
>> thanks in advance
>>
>> _______________________________________________
>> Help-octave mailing list
>> [hidden email]
>> https://lists.gnu.org/mailman/listinfo/help-octave
>
> This is the decomposition on base 10, a way of doing it is
>
> nc         = 3; # number of columns
> base     = 10;
> i            = (0:(base^nc-1)).'; # row index - 1
> counter = mod( floor (i ./ base.^[(nc-1):-1:0]), base);
>
> it should work for any integer base, but please do check.
Dear Juan,
I bumped into the following problem. I changed your code to a function
like this:

function [counter] = decomp (base, nc)
i            = (0:(base^nc-1)).'; # row index - 1
counter = mod( floor (i ./ base.^[(nc-1):-1:0]), base);
endfunction

It works fine for a lot of cases but the case I want to use is
problematic as you can see here:
result=decomp(10,9);
error: out of memory or dimension too large for Octave's index type
error: called from
    decomp at line 27 column 9


in fact I need decomp(10,10)

do you see a workaround for this problem?

kind regards,

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: how to make a matrix with all combinations of digits efficiently

Francesco Potortì
>2017-12-29 0:07 GMT+01:00 Juan Pablo Carbajal <[hidden email]>:
>> On Thu, Dec 28, 2017 at 9:25 PM, Jean Dubois <[hidden email]> wrote:
>>> I'd like to generate a matrix like this (small version to give you the idea):
>>>
>>> 0 0 0 (three columns in this example)
>>> 0 0 1
>>> 0 0 2
>>> 0 0 3
>>> .
>>> .
>>> .
>>> 9 9 8
>>> 9 9 9
>>>
>>> Could anyone here show me how to do this efficiently?

[...]

>Dear Juan,
>I bumped into the following problem. I changed your code to a function
>like this:
>
>function [counter] = decomp (base, nc)
>i            = (0:(base^nc-1)).'; # row index - 1
>counter = mod( floor (i ./ base.^[(nc-1):-1:0]), base);
>endfunction
>
>It works fine for a lot of cases but the case I want to use is
>problematic as you can see here:
>result=decomp(10,9);
>error: out of memory or dimension too large for Octave's index type

decomp(B,C) creates a matrix with B^C rows and C columns.  In the case
you tested this means 9e9 elements.  Each element is a double needing 8
bytes, which means that you need 72GB of memory only for hosting the
final result.  In practice, you need additional space for hosting
intermediate variables.

This is the only problem if Octave has been specially compiled for using
64-bit indexes, which is not the general case, and most probably not
your case.

For the general case, have a look at
https://wiki.octave.org/Enable_large_arrays:_Build_octave_such_that_it_can_use_arrays_larger_than_2Gb.

--
Francesco Potortì (ricercatore)        Voice:  +39.050.621.3058
ISTI - Area della ricerca CNR          Mobile: +39.348.8283.107
via G. Moruzzi 1, I-56124 Pisa         Skype:  wnlabisti
(entrance 20, 1st floor, room C71)     Web:    http://fly.isti.cnr.it


_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: how to make a matrix with all combinations of digits efficiently

jeandubois
2017-12-29 14:51 GMT+01:00 Francesco Potortì <[hidden email]>:

>>2017-12-29 0:07 GMT+01:00 Juan Pablo Carbajal <[hidden email]>:
>>> On Thu, Dec 28, 2017 at 9:25 PM, Jean Dubois <[hidden email]> wrote:
>>>> I'd like to generate a matrix like this (small version to give you the idea):
>>>>
>>>> 0 0 0 (three columns in this example)
>>>> 0 0 1
>>>> 0 0 2
>>>> 0 0 3
>>>> .
>>>> .
>>>> .
>>>> 9 9 8
>>>> 9 9 9
>>>>
>>>> Could anyone here show me how to do this efficiently?
>
> [...]
>
>>Dear Juan,
>>I bumped into the following problem. I changed your code to a function
>>like this:
>>
>>function [counter] = decomp (base, nc)
>>i            = (0:(base^nc-1)).'; # row index - 1
>>counter = mod( floor (i ./ base.^[(nc-1):-1:0]), base);
>>endfunction
>>
>>It works fine for a lot of cases but the case I want to use is
>>problematic as you can see here:
>>result=decomp(10,9);
>>error: out of memory or dimension too large for Octave's index type
>
> decomp(B,C) creates a matrix with B^C rows and C columns.  In the case
> you tested this means 9e9 elements.  Each element is a double needing 8
> bytes, which means that you need 72GB of memory only for hosting the
> final result.  In practice, you need additional space for hosting
> intermediate variables.
>
I wonder whether it is possible to make octave  store the array more
efficiently knowing that the elements are all
integers which can be represented by 1 byte
> This is the only problem if Octave has been specially compiled for using
> 64-bit indexes, which is not the general case, and most probably not
> your case.
>
> For the general case, have a look at
> https://wiki.octave.org/Enable_large_arrays:_Build_octave_such_that_it_can_use_arrays_larger_than_2Gb.
>
Unfortunately this wiki-page is empty

kind regards




> --
> Francesco Potortì (ricercatore)        Voice:  +39.050.621.3058
> ISTI - Area della ricerca CNR          Mobile: +39.348.8283.107
> via G. Moruzzi 1, I-56124 Pisa         Skype:  wnlabisti
> (entrance 20, 1st floor, room C71)     Web:    http://fly.isti.cnr.it

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: how to make a matrix with all combinations of digits efficiently

Francesco Potortì
>>>result=decomp(10,9);
>>>error: out of memory or dimension too large for Octave's index type
>>
>> decomp(B,C) creates a matrix with B^C rows and C columns.  In the case
>> you tested this means 9e9 elements.  Each element is a double needing 8
>> bytes, which means that you need 72GB of memory only for hosting the
>> final result.  In practice, you need additional space for hosting
>> intermediate variables.
>>
>I wonder whether it is possible to make octave  store the array more
>efficiently knowing that the elements are all
>integers which can be represented by 1 byte

Yes, you can, but reducing memory footprint is not so obvious, because
you should care about intermediate results.

>> This is the only problem if Octave has been specially compiled for using
>> 64-bit indexes, which is not the general case, and most probably not
>> your case.
>>
>> For the general case, have a look at
>> https://wiki.octave.org/Enable_large_arrays:_Build_octave_such_that_it_can_use_arrays_larger_than_2Gb.
>>
>Unfortunately this wiki-page is empty

Your mail client probably strips the last dot from the URL, try this
one:
<https://wiki.octave.org/Enable_large_arrays:_Build_octave_such_that_it_can_use_arrays_larger_than_2Gb.>

--
Francesco Potortì (ricercatore)        Voice:  +39.050.621.3058
ISTI - Area della ricerca CNR          Mobile: +39.348.8283.107
via G. Moruzzi 1, I-56124 Pisa         Skype:  wnlabisti
(entrance 20, 1st floor, room C71)     Web:    http://fly.isti.cnr.it


_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: how to make a matrix with all combinations of digits efficiently

Juan Pablo Carbajal-2
In reply to this post by jeandubois
> in fact I need decomp(10,10)

The issue with memory or index size are rather unavoidable. Do you
really need all this?
What is your intended use of counter? I am pretty sure you do not neet
to allocate nor have simultaneously such an enormous amount of
numbers.
Note that my solution works even for a single number "i", that means
you could call the function to decompose a given number everytime you
need a results, i.e.

function digits = dec2digit (num, base = 10)
nc      = ceil (log (num) / log (base));
digits = mod( floor (num ./ base.^[(nc-1):-1:0]), base);
endfunction

example

dec2digit (537)
ans =

   5   3   7

another one

d = dec2digit (707, 16);
n = length (d);
d * 16.^[(n-1):-1:0].'
ans =  707

another one

num = randi (10e10);
dec2digit (num)   # this one should be one of the ones you need.

If you are calling this from a loop, then you do not have memory
problems. You cna also use batches of numbers that follow a memory
restriction, i.e. work with batches of 1MB, then 1e6/8/10  is more or
less the number of rows of the matrix for that batch.

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: how to make a matrix with all combinations of digits efficiently

jeandubois
2017-12-29 19:13 GMT+01:00 Juan Pablo Carbajal <[hidden email]>:

>> in fact I need decomp(10,10)
>
> The issue with memory or index size are rather unavoidable. Do you
> really need all this?
> What is your intended use of counter? I am pretty sure you do not neet
> to allocate nor have simultaneously such an enormous amount of
> numbers.
> Note that my solution works even for a single number "i", that means
> you could call the function to decompose a given number everytime you
> need a results, i.e.
>
> function digits = dec2digit (num, base = 10)
> nc      = ceil (log (num) / log (base));
> digits = mod( floor (num ./ base.^[(nc-1):-1:0]), base);
> endfunction
>
> example
>
> dec2digit (537)
> ans =
>
>    5   3   7
>
> another one
>
> d = dec2digit (707, 16);
> n = length (d);
> d * 16.^[(n-1):-1:0].'
> ans =  707
>
> another one
>
> num = randi (10e10);
> dec2digit (num)   # this one should be one of the ones you need.
>
> If you are calling this from a loop, then you do not have memory
> problems. You cna also use batches of numbers that follow a memory
> restriction, i.e. work with batches of 1MB, then 1e6/8/10  is more or
> less the number of rows of the matrix for that batch.
Thanks a lot for all the help and suggestions offered, you are right
that I'll have to limit the number of cases involved first myself
rather
than presenting the problem in a brute force way which I first hoped to do.

kind regards,

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: how to make a matrix with all combinations of digits efficiently

jeandubois
In reply to this post by Juan Pablo Carbajal-2
2017-12-29 19:13 GMT+01:00 Juan Pablo Carbajal <[hidden email]>:

>> in fact I need decomp(10,10)
>
> The issue with memory or index size are rather unavoidable. Do you
> really need all this?
> What is your intended use of counter? I am pretty sure you do not neet
> to allocate nor have simultaneously such an enormous amount of
> numbers.
> Note that my solution works even for a single number "i", that means
> you could call the function to decompose a given number everytime you
> need a results, i.e.
>
> function digits = dec2digit (num, base = 10)
> nc      = ceil (log (num) / log (base));
> digits = mod( floor (num ./ base.^[(nc-1):-1:0]), base);
> endfunction
>
> example
>
> dec2digit (537)
> ans =
>
>    5   3   7
Dear Juan,
I just saw that dec2digit(100) produces 0 0 in stead of 1 0 0, so I
changed the function as follows
function digits = dec2digit (num, nc, base = 10)
%nc      = ceil (log (num) / log (base));
digits=mod(floor(num./base.^[(nc-1):-1:0]), base);


kind regards

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: how to make a matrix with all combinations of digits efficiently

Juan Pablo Carbajal-2
> I just saw that dec2digit(100) produces 0 0 in stead of 1 0 0, so I
> changed the function as follows
> function digits = dec2digit (num, nc, base = 10)
> %nc      = ceil (log (num) / log (base));
> digits=mod(floor(num./base.^[(nc-1):-1:0]), base);

a better fix is probably to force rounding up.

function digits = dec2digit (num, base = 10)
nc      = floor (log (num) / log (base)) + 1;
digits = mod(floor(num./base.^[(nc-1):-1:0]), base);
endfunction

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: how to make a matrix with all combinations of digits efficiently

Juan Pablo Carbajal-2
> a better fix is probably to force rounding up.

Well... better from the point of view of not allowing for inconsitent
inputs. But your is marginally faster, you could also cache the nc to
avoid re-computing it...but gain, it is marginal.

_______________________________________________
Help-octave mailing list
[hidden email]
https://lists.gnu.org/mailman/listinfo/help-octave