How to obtain all variations of an array with elements being zero or one

Question

I am going to write a do loop over possible values of an array elements. More specifically I have an array, say A(:) with size n and any element of array A can be 0 or 1. I want to iterate over all possible values of elements of A. Of course a simple way is

do A(1)=0, 1
 do A(2)=0, 1
  ....
   ! do something with array A

 end do 
end do

but the size of my array is large and this method is not very suitable. is there a better way to do this?

I'm not sure I got the question... Do you want to have all possible variations of the array with the elements being either zero or one? E.g.: `00`, `01`, `10`, `11` for an array of length two? — Alexander Vogt, Mar 25 '16 at 20:49
Dear Alexander, Yes, exactly. I want to have all possible variations of the array with the elements being either zero or one. But to save the memory I do not want to save all possible configurations in a larger Matrix. — Math-fort, Mar 25 '16 at 20:54
2^30 configurations. Indeed the size of A(:) is 30 and thus the total configurations are 2^30. — Math-fort, Mar 25 '16 at 20:57
Please also note that you must not change the loop index within the loop! Also, you cannot use elements of an array as a loop counter. — Alexander Vogt, Mar 25 '16 at 21:16
Related (although not for binary, but for arbitrary values): http://stackoverflow.com/questions/22285705/permutations-with-repetition-algorithm and http://stackoverflow.com/questions/35544443/getting-the-ith-permutation-of-a-list and http://stackoverflow.com/questions/24364332/algorithm-to-create-all-possible-combinations/24364575#24364575. — Alexander Vogt, Mar 25 '16 at 21:28

Alexander Vogt · Accepted Answer · 2016-03-26T20:21:08.583

Since this is binary only, why not (mis-)use integers for this task? Just increment the integer by one for each of the combinations and read out the corresponding bits using btest:

program test
  implicit none
  integer, parameter  :: n = 3
  integer             :: i
  integer             :: A(n)
  integer             :: idx(n) = [(i, i=0,n-1)] ! bit positions start at zero

  ! Use a loop to increment the integer
  do i=0,2**n-1
    ! Get the bits at the lowest positions and map true to "1" and false to "0"
    A = merge( 1, 0, btest( i, idx ) )
    print *,A
  enddo
end program

This simple code fills A with all combinations (one at a time) and prints them successively.

./a.out 
           0           0           0
           1           0           0
           0           1           0
           1           1           0
           0           0           1
           1           0           1
           0           1           1
           1           1           1

Note that Fortran only has signed integers, so the highest bit is not usable here. This leaves you up to 2^(32-1) combinations for (default) 4 byte integers if you start from zero as shown here (array length up to 31).

To get the full range, do the loop in the following way:

  do i=-huge(1)-1,huge(1)

This gives you the full 2^32 distinct variations for arrays of length 32.

thank you for your interesting solution. In the future I have to generalize my code for non-binary values. Is there a similar trick if the values of A(i) are 0,1,...,M.? — Math-fort, Mar 25 '16 at 21:22
@Math-fort Yes, but this general solution has been answered e.g., [here](http://stackoverflow.com/questions/22285705/permutations-with-repetition-algorithm) :) — Alexander Vogt, Mar 25 '16 at 21:27
Dear Alexander, Is there any way to handle an array of length `2^(32)`? thanks, :-( — Math-fort, Mar 26 '16 at 20:10

How to obtain all variations of an array with elements being zero or one

1 Answers1