All possible combinations problem


 
Thread Tools Search this Thread
Top Forums Shell Programming and Scripting All possible combinations problem
# 8  
Old 12-01-2015
Thank you for that code, it seems to work well.

I have checked the output on some patterns up to 5 on bits (5 1s) and it looks correct. As far as I can tell, there should be 2^n output patterns where n=the number of on bits. Do I have that right? For my test pattern of 5 on bits, there are 2^5=25 output patterns.

This is the output organized for simplified analysis,
Code:
# for the input pattern
bk_00110000000000110001000

# 4 on bits (change 1 1 to 0)
bk_00010000000000110001000
bk_00100000000000110001000
bk_00110000000000010001000
bk_00110000000000100001000
bk_00110000000000110000000

# 3 on bits (change 2 1s to 0)
bk_000000000000001100011000

bk_00010000000000010001000
bk_00010000000000100001000
bk_00010000000000110000000

bk_00100000000000010001000
bk_00100000000000100001000
bk_00100000000000110000000

bk_00110000000000000001000
bk_00110000000000010000000
bk_00110000000000100000000

# 2 on bits (change 3 1s to 0)
bk_00000000000000010001000
bk_00000000000000100001000
bk_00000000000000110000000

bk_00100000000000010000000
bk_00100000000000100000000
bk_00100000000000000001000

bk_00010000000000010000000
bk_00010000000000100000000
bk_00010000000000000001000

bk_00110000000000000000000

# 1 on bit (change 4 1s to 0)
bk_00000000000000000001000
bk_00000000000000010000000
bk_00000000000000100000000
bk_00010000000000000000000
bk_00100000000000000000000

As far as I can tell, this is what the output should be. Please let me know if anyone sees anything amiss.

The next thing I need to do is to add a function to check each subset generated against a list of subsets and look for matches.

My revised script looks like,
Code:
#! /bin/bash

function check_against {

   check_string=$1
   pattern_match=0

   # declare list of patterns to check agains
   check_list=( bk_00110000000000000001000 \
                bk_00110000000000000001000 \
                bk_00010000000000000001000 \
                bk_00010000000000000001000 \
                bk_00010000000000000001000 \
                bk_00010000000000000001000 \
                bk_10001010011100000101000 \
                bk_00001010111100000101000 \
                bk_10001110000000000101010 \
                bk_10001110000000110101000 \
                bk_11001110000000110101000 \
                bk_11110011011100110000000 \
                bk_00110000000000110000010 )

   # loop through check_list and compare each element to check_string
   for check_against_string in "${check_list[@]}"
   do
      if [ "$check_string" == "$check_against_string" ]; then
         pattern_match=$((pattern_match+1))
      fi
   done
   # if any matches were found, output match and number of matches
   if [ "$pattern_match" != "0" ]; then
      echo -e "$check_string\t$pattern_match"
   fi

}

# input string
input_string="${1:-"bk_00110000000000110001000"}"

# capture output of awk into string
subsets_list=$(

echo "$input_string" | awk -F1 '
# Compute 2**p - 1 for p >= 1
function two_e2m1(p,	i, v) {
	v = 0
	for(i = 1; i < p; i++)
		v = 2 * v + 1
	return(v)
}
NF {	printf("%s is input to be processed.\n", $0)
	for(i = two_e2m1(NF) - 1; i > 0; i--) {
		v = i
		for(j = 1; j < NF; j++) {
			d[NF - j] = v % 2
			v /= 2
		}
		for(j = 1; j < NF; j++)
			printf("%s%d", $j, d[j])
		print $NF
	}
}'

)

# parse subsets_list on newline
IFS=$'\n' read -rd '' -a check_list <<<"$subsets_list"

for element in "${check_list[@]}"
do
   # pass each element to check against function
   check_against $element
done

This is a bit of a hack, but I capture the output of Don Cragun's awk code in a string variable and then parse that into an array on newline. I then iterate through the array and pass each element to a function that compares the element against an array and counts the number of matches found. If any matches are found, the matching pattern is printed along with the number of matches.

This gives me the output I need as far as I can tell. Please let me know if anyone sees problems with this approach or has other suggestions.

LMHmedchem
# 9  
Old 12-01-2015
Please be aware that 2^5 = 32, not 25 (= 5^2).
If your input has all bits of interest set, and the all zero variant is to be excluded, you'll have 2^n - 2 patterns to work on.
This User Gave Thanks to RudiC For This Post:
# 10  
Old 12-01-2015
Quote:
Originally Posted by RudiC
Please be aware that 2^5 = 32, not 25 (= 5^2).
If your input has all bits of interest set, and the all zero variant is to be excluded, you'll have 2^n - 2 patterns to work on.
I guess my question at this point is whether or not the above code is giving my all of the combinations I am looking for. For the examples I tested, the output looks correct, meaning that I can't come up with any combinations that are missing. It also appears that I counted the output incorrectly. There are 30 subsets printed by Don Cragun's code, which matches your expected number.

My most complicated patter has 11 on bits, which corresponds to 2046 subsets according to your algorithm. Each of these will be checked against a check list of ~2000 patterns. This will likely not be lightning fast using the script above, but do you see any potential issues with memory?

LMHmedchem
# 11  
Old 12-01-2015
Holding two arrays of ~2000 elements each in memory shouldn't be too much a problem, but - without completely understanding your problem nor approach - there might be another approach that might work. Do you just need to check if the bits set in an input value are allowed by a "mask"? Then e.g. an "OR" operation might do...
# 12  
Old 12-01-2015
Quote:
Originally Posted by LMHmedchem
Thank you for that code, it seems to work well.

I have checked the output on some patterns up to 5 on bits (5 1s) and it looks correct. As far as I can tell, there should be 2^n output patterns where n=the number of on bits. Do I have that right? For my test pattern of 5 on bits, there are 2^5=25 output patterns.

This is the output organized for simplified analysis,
Code:
# for the input pattern
bk_00110000000000110001000

# 4 on bits (change 1 1 to 0)
bk_00010000000000110001000
bk_00100000000000110001000
bk_00110000000000010001000
bk_00110000000000100001000
bk_00110000000000110000000

# 3 on bits (change 2 1s to 0)
bk_000000000000001100011000

bk_00010000000000010001000
bk_00010000000000100001000
bk_00010000000000110000000

bk_00100000000000010001000
bk_00100000000000100001000
bk_00100000000000110000000

bk_00110000000000000001000
bk_00110000000000010000000
bk_00110000000000100000000

# 2 on bits (change 3 1s to 0)
bk_00000000000000010001000
bk_00000000000000100001000
bk_00000000000000110000000

bk_00100000000000010000000
bk_00100000000000100000000
bk_00100000000000000001000

bk_00010000000000010000000
bk_00010000000000100000000
bk_00010000000000000001000

bk_00110000000000000000000

# 1 on bit (change 4 1s to 0)
bk_00000000000000000001000
bk_00000000000000010000000
bk_00000000000000100000000
bk_00010000000000000000000
bk_00100000000000000000000

As far as I can tell, this is what the output should be. Please let me know if anyone sees anything amiss.

The next thing I need to do is to add a function to check each subset generated against a list of subsets and look for matches.

My revised script looks like,
Code:
#! /bin/bash

function check_against {

   check_string=$1
   pattern_match=0

   # declare list of patterns to check agains
   check_list=( bk_00110000000000000001000 \
                bk_00110000000000000001000 \
                bk_00010000000000000001000 \
                bk_00010000000000000001000 \
                bk_00010000000000000001000 \
                bk_00010000000000000001000 \
                bk_10001010011100000101000 \
                bk_00001010111100000101000 \
                bk_10001110000000000101010 \
                bk_10001110000000110101000 \
                bk_11001110000000110101000 \
                bk_11110011011100110000000 \
                bk_00110000000000110000010 )

   # loop through check_list and compare each element to check_string
   for check_against_string in "${check_list[@]}"
   do
      if [ "$check_string" == "$check_against_string" ]; then
         pattern_match=$((pattern_match+1))
      fi
   done
   # if any matches were found, output match and number of matches
   if [ "$pattern_match" != "0" ]; then
      echo -e "$check_string\t$pattern_match"
   fi

}

# input string
input_string="${1:-"bk_00110000000000110001000"}"

# capture output of awk into string
subsets_list=$(

echo "$input_string" | awk -F1 '
# Compute 2**p - 1 for p >= 1
function two_e2m1(p,	i, v) {
	v = 0
	for(i = 1; i < p; i++)
		v = 2 * v + 1
	return(v)
}
NF {	printf("%s is input to be processed.\n", $0)
	for(i = two_e2m1(NF) - 1; i > 0; i--) {
		v = i
		for(j = 1; j < NF; j++) {
			d[NF - j] = v % 2
			v /= 2
		}
		for(j = 1; j < NF; j++)
			printf("%s%d", $j, d[j])
		print $NF
	}
}'

)

# parse subsets_list on newline
IFS=$'\n' read -rd '' -a check_list <<<"$subsets_list"

for element in "${check_list[@]}"
do
   # pass each element to check against function
   check_against $element
done

This is a bit of a hack, but I capture the output of Don Cragun's awk code in a string variable and then parse that into an array on newline. I then iterate through the array and pass each element to a function that compares the element against an array and counts the number of matches found. If any matches are found, the matching pattern is printed along with the number of matches.

This gives me the output I need as far as I can tell. Please let me know if anyone sees problems with this approach or has other suggestions.

LMHmedchem
As RudiC has already stated, 2^5 is 32 (5^2 is 25). And the output my awk script produces for n "1" bits set is the input sample provided on the first line of output followed by ((2^n) - 2) lines treating the "1" bits in the input as bits in a binary number and each output line counts that binary number down from ((2^n)) - 1 to 1. Which is a trivial arithmetic progression that guarantees that there are no duplicates in the output. This approach should not have any problems at all until you get into a binary number big enough that awk would treat it as a floating point value instead of as an integer value. With the maximum of eleven "1" bits you stated would be present in your input samples, this will NOT be a problem.

It is not arranged by decreasing number of bits turned on as you do in your sample output "organized for simplified analysis". I find analyzing it that way to be much more difficult since you have to spend more time determining which subsets of the output should be included in each set. If you just look at the "1" bits in the output lines generated, the binary countdown should be easy to follow and verify as long as you understand what you're looking for.

If you really need a script to verify that the output my script produces does not include any duplicates, a very simple way to do that would be to use:
Code:
awk '$1 in a{print $0 "duplicated"}{a[$1]}END{print NR, "lines processed"}'

to filter the output produced by my earlier script. The value printed at the end should always be (2^n) - 1 where, again, n is the number of "1"s in the input string.

If you can't visually determine that the output produced from my script does not include any "1" bits where there weren't any "1" bits in the input, you could also verify that with an awk script, but given my confidence in my code, I won't take the time to write that additional script for you.
# 13  
Old 12-01-2015
Checking for a set bit outside a "mask" value can be easily done with "binary" operations; unfortunately, awk doesn't allow for this, afaik. bash can do it:
Code:
V1=$((2#1))
V8=$((2#01000))
MASK=$((2#11100))
echo $MASK
28
echo $((V1 | MASK))
29
echo $((V8 | MASK))
28
echo $(((V8 | MASK) == MASK))
1
echo $(((V1 | MASK) == MASK))
0

You see that bit0 is NOT in MASK, but bit7 is.
Login or Register to Ask a Question

Previous Thread | Next Thread

10 More Discussions You Might Find Interesting

1. Shell Programming and Scripting

awk permutations and combinations

hello, I'm reading this thread, in which there is this code :awk ' function comb(v,i) { for(i in A) { delete A; if(length(A)) comb((v?v"+":x)i) else print v"+"i A; } } { A } END { comb(); } ' infilebut I can't understand where does v come... (5 Replies)
Discussion started by: daPeach
5 Replies

2. Shell Programming and Scripting

All possible combinations

Hi, I have an input file like this a b c d I want to print all possible combinations between these records in the following way aVSb aVSc aVSd bVSc bVSd cVSd VS indicates versus. All thoughts are appreciated. (5 Replies)
Discussion started by: jacobs.smith
5 Replies

3. Programming

Words combinations without repetition

How can I get all combinations of 5 words from 10 words. For example I have 3 words and I want to get all combinations of 2 words. "A", "B", "C" it would like AB, BC, AC. Maybe you know some usefull code or example. Thanx a lot. P.S. Sorry if I'm not right enough cause I don't know English... (2 Replies)
Discussion started by: romeo5577
2 Replies

4. Shell Programming and Scripting

Combinations / Permutations

Hello Scrutinizer / Group , The shell script of awk that Scrutinizer made calculate all possible permutations in this case 3125 (5 numbers) but i want to have only the 126 possible combination. For now it does not matter the specific order of the combination numbers. I would appreciate it you... (1 Reply)
Discussion started by: csierra
1 Replies

5. Linux

Help with color combinations

Hi Team when i do, echo on my host box it returns (see below) # echo $PS1 \$ I need to set a color comination of my own for \u means for user : red for \h means for hostname: blue for \W means present working directory: pink for $ means for wht prompt : yellow Do i need to... (1 Reply)
Discussion started by: whizkidash
1 Replies

6. Programming

series of combinations

HI I have a series(sorted), which i require to create combinations. I am not getting the good code for doing this. My series should generate the following combinations... Please help me in getting this in C++. Thanks for your help. A: A A B: A B A B A B C: A ... (1 Reply)
Discussion started by: rameshmelam
1 Replies

7. Shell Programming and Scripting

Generating Combinations

Hi, I need to generate all combinations upto n-1 level, if the input file looks like say, A B C D . . .... I need to generate all combinations such that first value remains constant and the remaning are combined with all possible ways. Output A AB AC AD ABC (1 Reply)
Discussion started by: zorg4u
1 Replies

8. UNIX for Advanced & Expert Users

All Shortcut key combinations

Hi, I am using the Korn-Shell (ksh) and would like to know all the shortcut keys. For example: Shift + Insert etc. Thank you very much. Take care (0 Replies)
Discussion started by: --crimson--
0 Replies

9. UNIX for Advanced & Expert Users

Combinations

Hello All, i have two files, one of the format A 123 B 124 C 234 D 345 And the other A 678 B 789 C 689 D 567 I would like to combine them into one file with three columns: A 123 678 B 124 789 C 234 689 (4 Replies)
Discussion started by: Khoomfire
4 Replies

10. Shell Programming and Scripting

Grepping number combinations

Having problem in using the grep command to select all possible combinations a number in a file. Example: 123, I would like to grep the numbers 123,132,213,231,312 and 321. (2 Replies)
Discussion started by: wperry
2 Replies
Login or Register to Ask a Question