Script to find the available number possibilities


 
Thread Tools Search this Thread
Top Forums Shell Programming and Scripting Script to find the available number possibilities
# 1  
Old 03-20-2015
Question Script to find the available number possibilities

Hi,

I try to get the combination of 6 numbers from (1-60) using any script.
Any script that can help me to fix this ...

EG: The output should be like that different possibilities from 1-60...
1) 1 3 15 29 30 42
2) 4 5 6 31 44 60

like the above ... Hereas, I need all the possibilities of this combination.
# 2  
Old 03-20-2015
Are you sure you need all 60^6=46656000000 combinations?

With a recent bash, try sth. along this line:
Code:
 echo -e {1..6}" "{1..6}"\n"
 1 1
 1 2
 1 3
 1 4
.
.
.
 6 5
 6 6

# 3  
Old 03-20-2015
Hi RudiC,
I don't think it's that simple, in your example, 6 5 is wrong because 6 > 5

Regards.
# 4  
Old 03-20-2015
Judging by your last statement these two lines are considered wrong because there are previous numbers greater than the next one and numbers are duplicated:-
Code:
 23 4 7 13 49 33
 12 37 41 37 37 59

And that these two are not the same either even when the second line is sorted:-
Code:
 5 10 19 37 44 56
 37 5 10 56 19 44

I am not sure if this is close to, or absolutely, impossible with the number of combinations involved.
Try 3 numbers first from say 1 to 20 just to get your algorithm worked out and then see what tests are needed to filter out the oddities.
This means a possible 20^3, (8000), combinations which is easy to work with.
Not an easy task at all if speed is important...

(Are you trying to create a random number sequence generator for lottery ticket numbers?)

Last edited by wisecracker; 03-20-2015 at 06:21 PM.. Reason: Typo...
# 5  
Old 03-20-2015
Quote:
Originally Posted by gsiva
...
I try to get the combination of 6 numbers from (1-60) using any script.
Any script that can help me to fix this ...

EG: The output should be like that different possibilities from 1-60...
1) 1 3 15 29 30 42
2) 4 5 6 31 44 60

like the above ... Hereas, I need all the possibilities of this combination.
You haven't mentioned if the a number can repeat in the individual 6 slots. If a number cannot repeat, can a combination of the 6 numbers repeat? If neither of the above two things could happen, then we are looking at combinations of n numbers taken r at a time.

Case 1 - A number can repeat in all the slots. So, we have cases like:

1 1 1 1 1 1
1 1 1 1 1 2
1 1 1 1 1 3
...
...
2 2 2 2 2 2
2 2 2 2 2 3
...
There are 60^6 = 4.6 * 10^10 (about 46 billion) such possibilities.

Case 2 - A number cannot repeat but a combination can repeat, i.e. we are looking at permutations of n numbers taken r at a time. As an example, we could have cases like the following:

1 2 3 4 5 6
...
2 1 3 4 5 6
...
3 1 2 4 5 6
...

The numbers don't repeat in the individual slots, but permutations do repeat. Altogether, the 6 numbers are the same in the example above. In case of permutations, order is important.
For such an scenario, we have 60! / (60 - 6)! = 60! / 54! = 3.6 * 10^10 (about 36 billion) possibilities.

Case 3 - The numbers don't repeat and the combinations don't repeat either. These are combinations of n numbers taken r at a time. Examples:

1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 5 8
...
1 2 3 4 6 7
1 2 3 4 6 8
...
1 2 3 5 6 7
...

In case of combinations, order is not important.
There are 60!/ (54! * 6!) = 5.0 * 10^7 (about 50 million) such possiblities.

The first two cases should be easy to implement. I've posted a program to generate all possible combinations of n numbers taken r at a time. It's in Perl, in case that is an option.

Code:
$
$
$ cat -n combinations.pl
     1  #!/usr/bin/perl
     2  use strict;
     3  # =============================================================================
     4  # Generate the combinations of first n numbers taken r at a time.
     5  # Total number of combinations = n! / ( (n - r)! * r! )
     6  # We can compare the combination generation to the DFS traversal of a tree.
     7  # Given below is the sample tree for a case where n = 5, r = 3. There are
     8  # C(5,3) = 10 traversal paths in this tree.
     9  #
    10  #                 (Initial call)
    11  #                     |
    12  #          +---------------+----+
    13  #          1               2    3
    14  #          |               |    |
    15  #    +-------+----+      /  \   |
    16  #    2       3    4     3    4  4
    17  #  / | \    / \   |    / \   |  |
    18  # 3  4  5  4   5  5   4   5  5  5
    19  # =============================================================================
    20
    21  my $n = $ARGV[0];
    22  my $r = $ARGV[1];
    23
    24  my $fmt;
    25  foreach ( 0..$r-1 ) { $fmt .= "%-5s" }
    26  $fmt .= "\n";
    27  my @arr = ();
    28
    29  # =================================================================
    30  # Subroutine section
    31  # =================================================================
    32  sub print_array {
    33      my $arr_ref = shift;
    34      printf($fmt, @{$arr_ref});
    35  }
    36
    37  sub combinations {
    38      my ($aref, $ind, $value) = @_;
    39      my $ptr = $ind;
    40
    41      # The first if condition takes care of assigning the initial
    42      # values to the array until all elements are defined. Once that
    43      # is done, it sets the pointer to the leaf node.
    44      if (not defined $aref->[$ind]) {
    45          $aref->[$ind] = $ind + 1;
    46          if ($ind == 0) {
    47              print_array($aref);
    48              $ptr = $r - 1;
    49              $value = $aref->[$ptr];
    50          } else {
    51              $ptr = $ind - 1;
    52          }
    53      } else {
    54          # The comparison below determines the upper bound that can
    55          # be assigned to an element at a particular level.
    56          # If we can, we assign the value.
    57          # If we are at the leaf node, we print the array and call the function.
    58          # Otherwise, we move one step towards the leaf node and set the value for the next call.
    59          # If we cannot assign the value, we move one step towards the root node and call the function.
    60          # If we've gone beyond the root node, it's time to quit the recursive function.
    61          if ( $value + 1 <= $n + $ind - $r + 1 ) {
    62              $aref->[$ind] = $value + 1;
    63              if ( $ind == $r - 1 ) {
    64                  print_array($aref);
    65                  $value = $aref->[$ind];
    66              } else {
    67                  $value = $aref->[$ptr];
    68                  $ptr = $ind + 1;
    69              }
    70          } else {
    71              $ptr = $ind - 1;
    72              # termination condition
    73              if ( $ptr < 0 ) { exit }
    74              $value = $aref->[$ptr];
    75          }
    76      }
    77      # recursive call to the function
    78      combinations($aref, $ptr, $value);
    79  }
    80
    81  # =================================================================
    82  # Main section
    83  # =================================================================
    84  combinations(\@arr, $r-1, 0);
    85

$
$
$ perl combinations.pl 5 3
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
$
$ perl combinations.pl 6 3
1    2    3
1    2    4
1    2    5
1    2    6
1    3    4
1    3    5
1    3    6
1    4    5
1    4    6
1    5    6
2    3    4
2    3    5
2    3    6
2    4    5
2    4    6
2    5    6
3    4    5
3    4    6
3    5    6
4    5    6
$
$ perl combinations.pl 4 2
1    2
1    3
1    4
2    3
2    4
3    4
$
$ perl combinations.pl 7 5
1    2    3    4    5
1    2    3    4    6
1    2    3    4    7
1    2    3    5    6
1    2    3    5    7
1    2    3    6    7
1    2    4    5    6
1    2    4    5    7
1    2    4    6    7
1    2    5    6    7
1    3    4    5    6
1    3    4    5    7
1    3    4    6    7
1    3    5    6    7
1    4    5    6    7
2    3    4    5    6
2    3    4    5    7
2    3    4    6    7
2    3    5    6    7
2    4    5    6    7
3    4    5    6    7
$
$

# 6  
Old 03-21-2015
Hi.

Something similar using a CPAN module, adapted from the examples:
Code:
#!/usr/bin/env perl

# @(#) p3	Demonstrate module Math/Combinatorics.

use Math::Combinatorics;

my ( $min, $max ) = ( 1, 60 );
my @a1       = $min .. $max;
my @n        = @a1;
my $n        = 6;
my $combinat = Math::Combinatorics->new(
  count => $n,
  data  => [@n],
);

print "combinations of $n of [$min,$max]\n";
while ( my @combo = $combinat->next_combination ) {
  print join( ' ', @combo ) . "\n";
}

print "\n";

exit(0);

producing:
Code:
$ ./p3 | head -60 | specimen
Edges: 5:0:5 of 60 lines in file "-"
combinations of 6 of [1,60]
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 5 8
1 2 3 4 5 9
   ---
1 2 3 4 5 60
1 2 3 4 6 7
1 2 3 4 6 8
1 2 3 4 6 9
1 2 3 4 6 10

For an environment like:
Code:
OS, ker|rel, machine: Linux, 2.6.26-2-amd64, x86_64
Distribution        : Debian 5.0.8 (lenny, workstation) 
perl 5.10.0
head (GNU coreutils) 6.10
specimen (local) 1.17

The module also can do permutations. See https://metacpan.org/pod/Math::Combinatorics for more information.

Best wishes ... cheers, drl
This User Gave Thanks to drl For This Post:
Login or Register to Ask a Question

Previous Thread | Next Thread

10 More Discussions You Might Find Interesting

1. Shell Programming and Scripting

awk to find number in a field then print the line and the number

Hi I want to use awk to match where field 3 contains a number within string - then print the line and just the number as a new field. The source file is pipe delimited and looks something like 1|net|ABC Letr1|1530||| 1|net|EXP_1040 ABC|1121||| 1|net|EXP_TG1224|1122||| 1|net|R_North|1123|||... (5 Replies)
Discussion started by: Mudshark
5 Replies

2. Shell Programming and Scripting

Shell script to search a pattern in a directory and output number of find counts

I need a Shell script which take two inputs which are 1) main directory where it has to search and 2) pattern to search within main directory all files (.c and .h files) It has to print number of pattern found in main directory & each sub directory. main dir --> Total pattern found = 5 |... (3 Replies)
Discussion started by: vivignesh
3 Replies

3. Shell Programming and Scripting

Bash script to find the number of files and identify which ones are 0 bytes.

I am writing a bash script to find out all the files in a directory which are empty. I am running into multiple issues. I will really appreciate if someone can please help me. #!/bin/bash DATE=$(date +%m%d%y) TIME=$(date +%H%M) DIR="/home/statsetl/input/civil/test" ... (1 Reply)
Discussion started by: monasharma13
1 Replies

4. Shell Programming and Scripting

Find command possibilities

Using find command is the below possible ? find /home/abcd/****/efgh where the "****" can be any name/character. Thanks, Vasanth. (2 Replies)
Discussion started by: skcvasanth
2 Replies

5. Shell Programming and Scripting

Script to find the average of a given column and also for specified number of rows?

Hi Friends, In continuation to my earlier post https://www.unix.com/shell-programming-scripting/99166-script-find-average-given-column-also-specified-number-rows.html I am extending my problem as follows. Input: Column1 Column2 MAS 1 MAS 4 ... (2 Replies)
Discussion started by: ks_reddy
2 Replies

6. Shell Programming and Scripting

Script to find the average of a given column and also for specified number of rows??

Hi friends I have 100 files in my directory. Each file look like this.. Temp1 Temp2 Temp3 MAS 1 2 3 MAS 4 5 6 MAS 7 8 9 Delhi 10 11 12 Delhi 13 14 15 Delhi 16 17 ... (4 Replies)
Discussion started by: ks_reddy
4 Replies

7. UNIX for Dummies Questions & Answers

Script to find the number of tab delimiters in a line

Hi, I need to find the number of tab delimiters in the first line of a file.So using word=`head -1 files.txt` I have extracted the first line of file into a variable word.It has 20 tab delimted columns.So can anyone help me in finding the number of delimiters? I am using csh and I am a... (5 Replies)
Discussion started by: poornimajayan
5 Replies

8. Shell Programming and Scripting

script to find the average number or files?

Anyone has a script or command in UNIX that can take 4 to five different numbers and calculate the average? (2 Replies)
Discussion started by: bbbngowc
2 Replies

9. Shell Programming and Scripting

awk script to find the number of files

awk script to find the number of files in a directory with their date less than 15-oct-2006 please help (4 Replies)
Discussion started by: uni_ajay_r
4 Replies

10. UNIX for Dummies Questions & Answers

What can you do with unix what are the possibilities

Where do i get unix at (1 Reply)
Discussion started by: shinobikil
1 Replies
Login or Register to Ask a Question