Solved

how do I get all combinations of a set of constants?

Posted on 2013-12-08
11
208 Views
Last Modified: 2013-12-13
Suppose we have six constants: 1 through 6.

I would like to have a formula to get all combinations of of them,

I give an example of what I mean:

1 and 2 and 3 and 4 and 5 and 6
1 and 2 and 3 and 4 and 5, but not 6
1 and 2 and 3 and 4, but not 5 and 6
...
2 and 3 and 4 and 5 and 6, but not 1
3 and 4 and 5 and 6, but not 1 and 2
...
1 and 3 and 4 and 5 and 6, but not 2
1 and 4 and 5 and 6, but not 2 and 3
...
...
I Think you've got it.

Lastly, I'd put this in a php script to get the correct combination

if(1 and 2 and 3 and 4 and 5 and 6) {  do this  }
if(1 and 2 and 3 and 4 and 5)  {  do that  }

For me this is far over my training. Could you please lead me thorugh this.

Thanks.
0
Comment
Question by:lericson
11 Comments
 
LVL 108

Assisted Solution

by:Ray Paseur
Ray Paseur earned 100 total points
ID: 39704988
Have you tried to write any of the code for this?  If so, please show us what you've started so we don't waste your time repeating anything.

Is there a business reason for this?  It sounds so theoretical and academic that I think if you explain the business logic behind your application requirement we might be able to suggest something that would make sense.
0
 
LVL 11

Assisted Solution

by:Technodweeb
Technodweeb earned 100 total points
ID: 39704990
That is a lot of combinations... 6! or six factorial = 1*2*3*4*5*6=720
That makes for a whole lot of IF statements...
0
 
LVL 108

Expert Comment

by:Ray Paseur
ID: 39705018
With 720 if() statements, you might want to consider a switch construct.  But seriously, please show us what you've tried and what kind of output you're getting.  I am sure we can help.
0
 
LVL 108

Expert Comment

by:Ray Paseur
ID: 39705028
This might be one way of looking at the problem.

<?php // RAY_combinations_all_ordered_subsets.php
error_reporting(E_ALL);
echo "<pre>";


// PROBLEM: FIND ALL ORDERED SUBSETS OF A CHARACTER SET
// EXAMPLE: IN "ABC" IT MUST FIND "A", "AB", "BA", ETC.


// FUNCTION TO GENERATE THE COMBINATIONS OF CHARACTERS IN A STRING.
// OUTPUT IS AN ARRAY OF COUNT = strlen() FACTORIAL
// ADAPTED FROM http://cogo.wordpress.com/2008/01/08/string-permutation-in-php/
function string_combinations($str)
{
    if (strlen($str) < 2) return array($str);

    $combos = array();
    $endpop = substr($str, 1);

    // RECURSE
    foreach (string_combinations($endpop) as $permutation)
    {
        $length = strlen($permutation);
        for ($i = 0; $i <= $length; $i++)
        {
            $combos[] = substr($permutation, 0, $i) . $str[0] . substr($permutation, $i);
        }
    }
    return $combos;
}


// GENERATE THE COMBINATIONS OF ELEMENTS IN A ONE-DIMENSIONAL ARRAY
function array_combinations($arr)
{
    $return = array();

    // GET THE NUMERIC KEY RANGE OF THE INPUT ARRAY
    $str = implode('', range(0, count($arr)-1));

    // GET THE KEY COMBINATIONS
    $combos = string_combinations($str);

    // ITERATE OVER THE COMBINATIONS
    foreach ($combos as $combo)
    {
        $out = array();
        while (strlen($combo))
        {
           $key   = substr($combo,0,1);
           $combo = substr($combo,1);
           $out[] = $arr[$key];
        }
        $ndx = implode(NULL, $out);
        $return[$ndx] = $out;
    }
    return $return;
}


// DEMONSTRATE THE CODE
$abc = 'ABCDEF';
$abc = str_split($abc);
$cnt = count($abc) - 1;

// GET ALL LARGEST COMBINATIONS IN ARRAY FORMAT
$out = array_combinations($abc);
$out = array_keys($out);

// REDUCE THE STRING LENGTHS TO FIND SMALLER COMBINATIONS
while ($cnt)
{
    foreach ($out as $key)
    {
        $key = substr($key, 0, $cnt);
        $key = str_split($key);
        sort($key);
        $key = implode(NULL, $key);
        $new[$key] = $key;
    }
    $cnt--;
}

// WITH EACH OF THE REDUCED STRINGS, ADD ALL COMBINATIONS
foreach ($new as $abc)
{
    $arr = array_combinations(str_split($abc));
    $out = array_merge($out, array_keys($arr));
}

// SHOW THE WORK PRODUCT
sort($out);
echo "FOUND " . number_format(count($out)) . " COMBINATIONS";
echo PHP_EOL;
print_r($out);

Open in new window

0
 
LVL 32

Assisted Solution

by:phoffric
phoffric earned 100 total points
ID: 39705034
>>  6! or six factorial = 1*2*3*4*5*6=720
But in the question, ordering of the conditions doesn't matter, so 720 is too high.

Is
if not any, then do this
one of the options? If it is then you have 2^6 = 64 conditions. (Think of a 6 bit flag where if a bit is set, then that condition is required, and if not set, then that condition must be false.)

Now, do you actually have 64 do this or that? If not, group the conditions into families associated with each of the  do this or that.
0
Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

 
LVL 32

Expert Comment

by:phoffric
ID: 39705048
>> if(1 and 2 and 3 and 4 and 5)  {  do that  }
Just noticed this condition which is not the same as:
     if(1 and 2 and 3 and 4 and 5 and not 6)  {  do that  }

Your previous examples always had 6 conditions in them, but this one has only 5. Is that your intent?
0
 
LVL 32

Expert Comment

by:phoffric
ID: 39705050
Is this question related to coursework - homework or otherwise? If so, then you should provide us with what you have and ask a specific question about a problem since EE policy says that we provide guidance but not solutions to academic type questions.
0
 
LVL 27

Assisted Solution

by:d-glitch
d-glitch earned 100 total points
ID: 39705126
The max number of combinations is 2^6 = 64, not 6! = 720.

The way to enummerate, test, and act on them is with a 6-bit binary field or number.

000000  ==> no conditions
000001  ==> condition 1
000010  ==> condition 2
000011  ==> conditions 1 and 2
. . .
111110 ==> all but 1
111111 ==> all  six conditions
0
 
LVL 32

Expert Comment

by:phoffric
ID: 39705131
>> The max number of combinations is 2^6 = 64, not 6! = 720
Thanks for agreeing with me. But as I asked the author, if his last test of
if(1 and 2 and 3 and 4 and 5)  {  do that  }
is really what he meant, then there are more than 64 combined conditions to consider.
0
 
LVL 84

Accepted Solution

by:
ozo earned 100 total points
ID: 39705251
Counting cases where we don't care about some of the conditions would give 3^6 combinations, but some of them would then be overlapping, since
if(1 and 2 and 3 and 4 and 5)  covers both if(1 and 2 and 3 and 4 and 5 and 6) and if(1 and 2 and 3 and 4 and 5 and not 6)
so there would still be no need for more than of 2^6 separate if statements.
Which is still a large enough number that you'd probably prefer to use a table rather than individual if statements.
0
 

Author Comment

by:lericson
ID: 39715867
Thanks for all your replies. This is far beyond what I had in mind. I appreciate your willingness to help. I want to Close this matter now.
0

Featured Post

How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
Router for PHP reqeusts 12 32
Time difference 10 35
session dropped in IE 10 20
Wordpress update causing pages to crash 1 19
Author Note: Since this E-E article was originally written, years ago, formal testing has come into common use in the world of PHP.  PHPUnit (http://en.wikipedia.org/wiki/PHPUnit) and similar technologies have enjoyed wide adoption, making it possib…
Things That Drive Us Nuts Have you noticed the use of the reCaptcha feature at EE and other web sites?  It wants you to read and retype something that looks like this.Insanity!  It's not EE's fault - that's just the way reCaptcha works.  But it is …
Learn how to match and substitute tagged data using PHP regular expressions. Demonstrated on Windows 7, but also applies to other operating systems. Demonstrated technique applies to PHP (all versions) and Firefox, but very similar techniques will w…
The viewer will learn how to create and use a small PHP class to apply a watermark to an image. This video shows the viewer the setup for the PHP watermark as well as important coding language. Continue to Part 2 to learn the core code used in creat…

705 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now