×
INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Log In

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!

*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Students Click Here

sunsets of a set
2

sunsets of a set

sunsets of a set

(OP)
Hello everyone,

I need to generate all the possible combinations of a set (in my case my set has 32 elements) and I need all possible subsets of 16 elements.
So, anyone have any idea how to do this?

There are subroutines and I have tried, however, documentation is not clear enough. So, if someone knows how to do this either by using a subroutine or by writing a code I would appreciate it.

Thanks and regards,

Ignacio

RE: sunsets of a set

Have you tried the brute force method with 16 nested loops?

RE: sunsets of a set

(OP)
Hello,

I have not tried yet, I am a bit new in FORTRAN... so, if you could give me an example it would help me a lot.

Thanks and kind regards,

RE: sunsets of a set

Take a simple example 5 numbers 3 combinations. So that will be 5C3 where n = 5 and r = 3. Let us work it out manually. Always start with something small that you can work through manually. The combinations will be

CODE

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5 
A program will do exactly the same thing. Look at the first column. Notice how the first 6 start with 1, the next 3 start with 2 and the last one starts with 3. So your fist loop goes from 1 to (n - r + 1). Try it out

CODE

do i1 = 1, n - r + 1
    write(*,*) i1
end do 
Now look at the second column. It goes from 2 to 4. i.e. from i1 + 1 to n - r + 2. Try it out

CODE

do i1 = 1, n - r + 1
    do i2 = i1 + 1, n - r + 2.
        write(*,*) i1, i2
    end do
end do 
Now look at the third column. It goes from 3 to 5 i.e. from i2 + 1 to n - r + 3

So now you have your 3 loops.

CODE

do i1 = 1, n - r + 1
    do i2 = i1 + 1, n - r + 2
        do i3 = i2 + 1, n - r + 3
            write(*, *) i1, i2, i3
        end do
    end do
end do 
That just prints the indices. OK now what happens if your numbers are not 1, 2, 3, 4, 5 but 3, 21, 16, 2, 5

CODE

integer, parameter:: n = 5, r = 3
integer:: num(n), comb(r)
! first stick them into an array
num = (/ 3, 21, 16, 2, 5 /)
! now pick out the indices
do i1 = 1, n - r + 1
    comb(1) = num(i1)
    do i2 = i1 + 1, n - r + 2
        comb(2) = num(i2)
        do i3 = i2 + 1, n - r + 3
            comb(3) = num(i3)
            write(*, *) (comb(ii), ii = 1, r, 1)
        end do
    end do
end do 
Notice where the 1, 2 and 3 appear. There is a pattern there - I'll leave you to figure it out. Don't write the whole program in one go. Do a little bit at a time and then try it out. Once you are happy with it, move to the next stage.

RE: sunsets of a set

(OP)
Hello,

First of all thank you so much for your reply and time.

I am going to check it and try to understand the meaning of these loops.
I know how to use loops but this is the very first time that I see this notation in loops.

Thanks again, I really appreciate it.

RE: sunsets of a set

(OP)
Dear xwb's,

First of all, the code works perfectly and thanks for that. I just have some doubts due to my lack of experience in FORTRAN.

1.The 'i1' that you used in the loop, it is not specified in the variables section, and as far as I know it should be declared as an integer. It's clear that the code works but I don't get why you did not declared it.

2. Is there a way to storage every output (subset) into a separate file?

3. Could you give me a brief explanation of this: (comb(ii), ii = 1, r, 1). I am completely lost in this statement (of course, I know that you are printing out the results, but the reason of had used ii=1,r,1 is completely out of my understanding right now).

Sincerely,

Ignacio


RE: sunsets of a set

1) By default, variables beginning with letters I to N are integer. They really ought to be declared but I was more concerned about going through the motions of developing a program than the syntax.
2) Yes, you need to look at the open, write and close statements. Try https://www.tutorialspoint.com/fortran/fortran_fil...
3) That is an implied do loop which prints elements comb(1) to comb(r). If you just look up implied do loop, there are lots of hits.

RE: sunsets of a set

I found nice iterative algorithm for generating combinations in lexicographic order on https://www.baeldung.com/java-combinations-algorit....
For example, for n = 5 and r = 3 it generates combinations starting from

CODE

1  2  3 
in lexicographic order until

CODE

3  4  5 
How it works: We set the initial combination = [1, 2, 3] and increase it by
combination(3) = combination(3) + 1 until combination(3) = 5, i.e. we generate:

CODE

1  2  3
1  2  4
1  2  5 
now combination(3) = 5 so we change to combination(2) and increase it
combination(2) = combination(2) + 1 and set
combination(3) = combination(2) + 1 i.e.

CODE

1  3  4 
and then combination(3) = combination(3) + 1 until combination(3) = 5, i.e.:

CODE

1  3  5 
now combination(3) = 5 so we change to combination(2) and increase it
combination(2) = combination(2) + 1

CODE

1  4  5 
now combination(3) = 5, combination(2) = 4 so we change to combination(1) and increase it by
combination(1) = combination(1) + 1 and for i = 2, 3 we set
combination(i) = combination(i - 1) + 1

CODE

2  3  4 
then combination(3) = combination(3) + 1

CODE

2  3  5 
now combination(3) = 5 again so we increase combination(2) = combination(2) + 1 and get

CODE

2  4  5 
now combination(3) = 5, combination(2) = 4 so we change to combination(1) and increase it by
combination(1) = combination(1) + 1 and get finally

CODE

3  4  5 

Here is the program:
combinations.f95

CODE

program combinations_test
  implicit none
  integer, dimension(:, :), allocatable :: combinations
  integer :: n, r, nr_comb

  n = 5
  r = 3
  !n = 32
  !r = 16
  call combination_generator(n, r, .true.)
end program combinations_test

subroutine combination_generator(n, r, print_combinations)
  ! see:
  ! https://www.baeldung.com/java-combinations-algorithm
  integer, intent(in) :: n
  integer, intent(in) :: r
  logical, intent(in) :: print_combinations
  integer, dimension(r) :: combination
  integer :: t, i, k
  10 format('Generated Combinations C(',i2,',',i2,'):')
  20 format('C(',i2,',',i2,') =')

  do i=1, r
    combination(i) = i
  end do

  ! write header
  if (print_combinations) then
    write(*,10) n, r
  end if    
  k = 0
  do while(combination(r) <= n)
    k = k + 1
    if (print_combinations) then
      ! write one combination
      do i=1, r
        write(*,'(i3)',advance='no') combination(i)
      end do
      write(*,*)
    end if

    ! generate next combination in lexicographic order
    t = r
    do while ((t .ne. 1) .and. (combination(t) .eq. n - r + t))
      t = t - 1
    end do
    combination(t) = combination(t) + 1
    do i = t + 1, r
      combination(i) = combination(i - 1) + 1
    end do
  end do
  ! write nCr:     
  write(*,20, advance='no') n, r
  write(*,*) k
  write(*,*)
end subroutine combination_generator 

You could get the resulting combination into the file using redirection:

CODE

$ ./combinations > combinations_out.txt 

For bigger n, r use first rather

CODE

call combination_generator(n, r, .false.) 
so the subroutine only computes the binomial coefficient C(n,r) and will not write the combinations, because writing large files will take very much time.
For example for n = 32, r = 16 it computes C(32,16) = 601080390. Creating the file with all combinations took very long time and the file has 28 GB. I cannot open it in editor, only display it's head and tail:

CODE

$ head combinations_32_16_out.txt 
Generated Combinations C(32,16):
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 17
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 18
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 19
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 20
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 21
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 22
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 23
  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 24
$ tail combinations_32_16_out.txt 
 16 17 18 19 20 21 22 24 25 26 27 28 29 30 31 32
 16 17 18 19 20 21 23 24 25 26 27 28 29 30 31 32
 16 17 18 19 20 22 23 24 25 26 27 28 29 30 31 32
 16 17 18 19 21 22 23 24 25 26 27 28 29 30 31 32
 16 17 18 20 21 22 23 24 25 26 27 28 29 30 31 32
 16 17 19 20 21 22 23 24 25 26 27 28 29 30 31 32
 16 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
C(32,16) =   601080390 














RE: sunsets of a set

(OP)
Hi Mikrom,

Thanks for the detailed explanation, I appreciate it.

Regarding the file size, Yes it is huge. I need this code because I am writing a Monte Carlo Simulated Annealing (MC-SA) and I need to explore the arrangements of a particular crystal and each arrangement of 16 numbers [between 1-32] represent the indices of a set of 3D coordinates. Basically after generate an arrangement I need to pass it to another particular array, then explore/study it (By using MC-SA) and then do the same with the next array, so, technically speaking I don't need to store them in a file.

I've got one last question and it is about MPI: Is it possible to use MPI in a code like this?
As far as I know I would make the code run faster... Right?

I am sort of new in this "FORTRAN world", so I know how to implement some tasks but definitely some task surpass by much my skills... So, I am trying learn and understand as much as I can. So, If you know any book/manual or YouTube channel that you can recommend, it would be really helpful.

Once again, thank you so much.

Kind regards,

ignacio

Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Tek-Tips Forums free from inappropriate posts.
The Tek-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members! Already a Member? Login

Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close