Algorithm to find the minimum number of combinations required

[it@61@sec]

I have an outcome (O) which could have three states: octal 4, octal 2 or octal 1.
With three such outcomes I have 27 combinations.
The challenge is to find an algorithm which gives me the minimum number of combinations (NK) which always gives me minimum 2 of 3 states correct.
An example: The combinations 4-4-4 covers the following combinations: 4-4-4, 4-4-2, 4-2-4, 2-4-4, 4-4-1, 4-1-4, 1-4-4 given this requirement.
Mathematically this could be done with only 4 combinations, but how do I find them ???
(The total challenge covers 2-3 states and up til 12 outcomes).

[rproffitt]

This looks like it was kicked around before. Here's how I found the prior posts on this.
https://www.google.com/search?q=With+three+such+outcomes+I+have+27+combinations

[it@61@sec]

I know permutation, and I know how to calculate permutations. The question is HOW to find the combinations which gives me 2 out of 3 for each of them in the example above.

If you have 4 outcomes with 3 states each you have 4^3 = 81 different combinations.
Mathematically you need 81 / 9 = 9 combinations to fullfill this requirement to give you 3 out of 4 correct states.
If you use 4, 2 and 1 as the different states you have these 9 combinations which gives you 3 out of 4 states no matter which of the 81 different combinations you try...

O1: 1 4 2 1 4 2 1 4 2
O2: 2 4 1 4 1 2 1 2 4
O3: 4 2 1 1 4 2 2 1 4
O4: 4 4 4 2 2 2 1 1 1

You have 4 correct states in 9 out of 81, and 3 correct states + 3*2 correct states in 72 out of 81 combinations.

I'm looking for an algorithm which gives me these 9 combinations when I know that there are 81 combinations for all.

[rproffitt]

I know permutation, and I know how to calculate permutations. The question is HOW to find the combinations which gives me 2 out of 3 for each of them in the example above.

OK, you know step 1. Now in your code write a function to test each permutation for your "correct" result. Your choice to store that set or just add +1 to the number of sets that met the test.

[it@61@sec]

Let's call the maximum number of permutations for A, and the subset I'm looking for B.
(In my example A equals 81 combinations, and B equals 9 combinations).

A is known, but B is unknown.
(In my example I used an "old" and well-known "solution").

Then I'll have to pick the first combination in A and find out which other combinations fullfills the requirement.
Let's call these other combinations C.

So I must exclude the C combinations from A, and find the next combination in A which could be used to check the remaining combinations (and so on).

But then again: How will I know that this will give me the minimum number of combinations ? It's not given that I should start with the first combination in A.. (And what a large job this would be if I tried to run 12 outcomes with 3 states for each: 3^12 = 531 441 combinations..)

So I really need some other thoughts on this...
(NOTE: I did a typo error in my last post: It's 3^4 = 81 combinations, not 4^3.. )

[AssertNull]

"Permutations" and "combinations" have specific definitions in Combinatorics/Probability. 4-4-4 would not be a permutation since repeats are not allowed. Ditto combinations. Combinations are permutations where the order does not count, so 1-2-4 and 4-2-1 would be different permutations, but the same combination. Thus any formula taking an exponent to a power would be neither a combination or permutation. I imagine it would be some type of multinomial, but don't quote me.

Not saying you can't use the terms, but be aware and make sure the reader is aware of whether you're using them in their technical "term of art" specific definitions so no one is confused.

I'd say this is a fantastic candidate for a dumb-and-dirty inefficient brute force programming solution. I started one, but got busy. Computing resources are cheap. Sure there is math involved when the number of trials and/or possible outcomes gets big, BUT with the small and medium numbers, inelegant brute force is easier than mathematical analysis and you should solve it for enough scenarios that you'll see a pattern, and much quicker than you'd solve it mathematically (actually I'll just speak for myself here0. So you find the pattern using dumb brute force computing, then you turn that pattern into a smarter non-brute-force algorithm, then you're home free.

If you have 3 outcomes and 4 trials, as you have, you can take any value (4-2-1-4) and you have eight ways ((3 minus 1) times 4) to change one digit in the 4 digit number. Add in the original value and "4-2-1-4" "covers" 9 values, including itself. With 81 possibilities, 81 divided by 9 is 9 so you'll need AT LEAST 9 values to "cover" all 81 possibilities.

That's if all these sets are disjoint / don't overlap with each other. Can you choose 9 values where there is no overlapping? I don't know. Either do the math/diagram approach or do the brute force approach to find out. Again, I vote brute force at first, find the pattern, then back into a more elegant solution that you can write up.

[it@61@sec]

AssertNull:
I wondered if it was correct to use the terms "permutations" and/or "combinations" in this question, but I had to name it something.. .:-)

So I think I'll go further with the "brute force" method, and then try to refine it if I find some pattern I could follow..

This project is about doing predicitions for soccer games (which could have three outcomes: home win, draw or away win, hence using the terms 4-2-1 which again could be regarded as octal values => binary: 100 - 010 - 001). In my country we have the possibility to bet for 12 games three times a week, both fulltime or halftime. 12 games with 3 outcomes gives 3^12 possible results ==> 531 441. And usually there is cash prizes if you have 12, 11 or 10 correct results... :-)

Most of my program is already finished (for the moment I'm using Gambas as programming language), but this challenge is really a challenge..

[AssertNull]

GAMBAS, huh? Are you a student? Is this for a class? I'm not knocking BASIC, to each their own. However, in this case (and most cases), I believe C++ is the way to go. I see this type of problem as a combination of low-level C-type number manipulations and higher-level C++ built-in options such as the Standard Template Library and the Algorithm methods, which are not available in C.

The early brute force trials with low values can be done in anything that you are comfortable in, but C++ potentially offers speed and efficiency unmatched in any other language IMO, so if you plan to do a lot of projects like this, I'd put C++ on your "to learn" list, study up on Combinatorics/Probability and find out if there are software/libraries that already does stuff like this (ie Mathematica or Boost). In the end, it's usually a matter of a little bit of "write your own", a little bit of research, a little bit of using what is already out there, a little of bit of brute force, a little bit of math, a little bit of programming, a little bit of doing it the "dumb way", a little bit of thinking it through and doing it the "smart way", and a lot of experimenting till you find the answer and the right balance.

You'll rarely find any of these libraries written and released using any type of BASIC, so if you go that route, you'll be doing quite a bit of "roll your own".

What you DON'T want to do is spend six months figuring out the absolutely most efficient way to do this mathematically and programatically. You USED to have to do this (and sometimes you still do), but I still often see people having flashbacks to the 1960's when you had to pay exorbant rates to get computer processing time. Back then computer time was expensive compared to programmers' time. Now, with Moore's Law and all that, the difference between an efficient and an inefficient program is 12 milliseconds of runtime on a computer using 5% of its resources. I knew a guy who spent a week comparing Big-O values to sort twenty values instead of writing a Bogo-sort in a few minutes. Efficiency is leaving the office at 5 pm with an e-mail saying "Boss, I'm done. It ain't perfect, but it's good enough."

Not sure why I decided to go off on this rant, but if you can find something useful in it, my work here is done. :)

[it@61@sec]

@AssertNull

I did this project in Gambas because it was the easiest way for me to get it "on the run" so that I could use it as fast as possible.. :-)
The program I'm developing does all the job for me so that I can deliver my systems for soccer betting whenever I want (and it is the first program of it's kind which is written exclusivly for the Linux platform).

GAMBAS is an excellent tool to get things running in a fast way. Maybe I'll transform it to C++ sometime in the future.

And I'm not a student. In fact I had to retire from work 5 years ago due to health problems, and before that I worked 25 years in the IT-industry. Mainly on support, but also on network and security. And programming has been my hobby for years...

[AssertNull]

I played around with this a little myself, got some weird segmentation faults, started to debug, then realized I don't have that luxury since I have a full plate of stuff I have to do. Still, intriguing problem. Please do post back if you end up solving it and it's postable and not copyrighted, etc. Good luck.

[AssertNull]

OK, as usual with me, my REAL work that I get paid for had to be put on the back burner until I solved this problem. And I do believe I have. Consider 4 games, each with the three possibilities you mentioned (home win = 4, draw = 2, home lose = 1). I had my program use 2,1,0 instead of 4,2,1, but I believe that's irrelevant. Below is, I believe, a successful solution to this problem, assuming I understand it correctly...

1-1-1-1
1-2-2-2
1-4-4-4
2-1-2-4
2-2-4-1
2-4-1-2
4-1-4-2
4-2-1-4
4-4-2-1

There are 3 to the 4th power (3 possible outcomes per game, 4 games) equals 81 possible "combinations" (again, see above for wording disclaimer, I'm simply not sure what the correct word is myself -- I used to know, but I believe we're on the same page here, semantics aside so it's all good). Each of the 9 combinations above "covers" 9 possible outcomes. 9 times 9 is 81, so I believe it is mathematically impossible to "cover" all possibilities with FEWER than 9 combinations, so if the 9 above in fact work, I believe this is an "optimal" solution.

Now I believe that the key to this is that each of the 81 combinations is "covered" by one of the 9 above, and no combination is "covered" by MORE than one of the 9 above. Pick any pair of the 9 and make sure that they have at most one value in common. Any MORE than 1 value will cause them to have a duplicate "cover".

For example, 1-1-1-1 and 2-1-2-4 each have 1 as the 2nd digit, but no other matches, so there are no mutual "covered" possibilities, whereas 1-1-1-1 and 1-1-2-4 would both "cover" 1-1-2-1, which is bad.

Anyway, if you could confirm that the above is indeed a solution and that I'm interpreting the problem correctly, I'd appreciate it. If so, and if you are still interested, I'd be willing to spend a LITTLE more time cleaning up the code to generate solutions for (n, k) where n is the number of games (4 in this case) and k is the number of possible outcomes per game (3 in this case - win/lose/draw). Lemme know. Fun problem. I really hope I in fact interpreted the problem correctly and actually solved it.

[JamesCherrill]

minimum 2 of 3 states correct

I've been trying to follow this topic, but am still stuck on the first paragraph. What is the formal definition of "correct" in this context?

[AssertNull]

Hopefully the OP will come back, but MY interpretation is as follows. Let's say four soccer games are played with the following results...

Game 1 - Home team wins (4)
Game 2 - Home team wins (4)
Game 3 - Draw (2)
Game 4 - Home team loses (1)

So the result is 4-4-2-1

What people do is bet on the results, so suppose I bet as follows...

Game 1 - Home team loses (1)
Game 2 - Home team wins (4)
Game 3 - Draw (2)
Game 4 - Home team loses (1)

My bet would be 1-4-2-1

The rule appears that I "win" the bet if I get at most one game wrong, so you compare each digit with the results. Any match would be "correct".

4-4-2-1 (actual results)
1-4-2-1 (my bet)
I-C-C-C (I represents incorrect, C reepresents correct. I got one incorrect, so I "win" the bet since the definition of "winning" is guessing at most one game wrong.

My bet of 1-4-2-1 would "cover" all possible results where my bet would "win". There are 9 results where I would win. If any of the following results occur, my bet of 1-4-2-1 "wins"...

1-4-2-1 (all right)
0-4-2-1 (game 1 wrong)
2-4-2-1 (game 1 wrong)
1-1-2-1 (game 2 wrong)
1-2-2-1 (game 2 wrong)
1-4-1-1 (game 3 wrong)
1-4-4-1 (game 3 wrong)
1-4-2-2 (game 4 wrong)
1-4-2-4 (game 4 wrong)

The goal is to figure out a bunch of bets (the fewest possible) where at least one bet will win no matter what the results are. I believe my earlier post was such a solution...

1-1-1-1
1-2-2-2
1-4-4-4
2-1-2-4
2-2-4-1
2-4-1-2
4-1-4-2
4-2-1-4
4-4-2-1

Unless I messed up, any of the 81 possible results (3 to the 4th power) will have at least one of the nine bets above "win". There will in fact be EXACTLY one winning bet, which is the key to the problem.