I have to create all possible combinations of some string data and if possible, would like to be able to do this with a script instead of a full blown cpp program.
The input data is string and looks like, b_00000000011100000000000
For a given input string, I need to generate all of the strings that could be considered subsets of the input. This just means any combination of matching 1s up to n-1. The leading b_ is not relevant. For example,
This is fairly straightforward for a string with three 1s, but I have strings with up to 10 1s, so this needs to be done algorithmically. If there were 10 1s, I would need to generate all of the overlapping patterns of 9 1s and smaller.
I guess if I was programming this in cpp, I would start with each single 1 and then add each other 1 to make all of the pairs, then use the pairs to make the triplets, etc. Code for this kind of thing often looks like creating paths with a breadth first search, like adding neighbor vertex numbers. I have no idea how to do that kind of thing in a scripting language.
If anyone can give me some suggestions, that would be a big help.
Somehow, my post came on top of the thread instead of the last post, whereas post #2 is the original post.. Hmm.. No sure how to correct this...
Have not got time for it now...
This User Gave Thanks to Scrutinizer For This Post:
You can see that there are missing 0s for some of the output strings. In some cases, there is one 0 missing, in others, there are two.
I could probably hack this to replace space with 0 if necessary. I am also wondering if this would work with non-consecutive 1s such as for the example.
b_10000000000100000000001
or
b_00000000010110000000000
etc.
I tried the above script with an input string with many more 1s and there is no output at all. This is the string I tried.
You do realise that this 23 bit word would give 8388607 combinations if all bits were set to 1?!
Is this a possibility along with just any single random bit which would not have a subset at all...
Or am I missing something?
Yes, this is theoretically true. In my data, the most complex example has 11 bits set to 1. That is still quite a large number of combinations. There will never be a case with 0 on bits, but there will be some with 1 on bit that has no subsets as you point out.
It may be sufficient for me to analyze subesets up to some size, such as 5 on bits or something like that, I don't know yet.
At any rate, one of the reasons to use an automated algorithm is to be able to chew through very large numbers of permutations. At the end of the day, I need to compare the all possible subsets list to an actual list to see how many matches there are. The total number of matches will be very small, even if the list of possible matches is on the order of 10^7. I really don't care very much if this takes a long time to run (as long as it's not days), so I just have to get this automated so I can start looking at results.
If I correctly understand what you're trying to do (and I'm not sure that I do), you might want to try:
Code:
#! /bin/bash
input_string="${1:-"bk_00000000011100000000000"}"
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
}
}'
which, when invoked with no operands produces the output:
Code:
bk_00000000011100000000000 is input to be processed.
bk_00000000011000000000000
bk_00000000010100000000000
bk_00000000010000000000000
bk_00000000001100000000000
bk_00000000001000000000000
bk_00000000000100000000000
and, when invoked with the operand bk_001001001001000000000produces the output:
Code:
bk_001001001001000000000 is input to be processed.
bk_001001001000000000000
bk_001001000001000000000
bk_001001000000000000000
bk_001000001001000000000
bk_001000001000000000000
bk_001000000001000000000
bk_001000000000000000000
bk_000001001001000000000
bk_000001001000000000000
bk_000001000001000000000
bk_000001000000000000000
bk_000000001001000000000
bk_000000001000000000000
bk_000000000001000000000
As always, if you want to try this on a Solaris/SunOS system, change awk to /usr/xpg4/bin/awk or nawk.
This User Gave Thanks to Don Cragun For This Post:
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)
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)
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)
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)
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)
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)
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)
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)
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)
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)
11-30-2015
