0
$\begingroup$

Lets say we are trying to find all combinations of length $n$ of digits from {$1,2,3,4,5,6$} such that the average of the digits of a string is greater than or equal to ($\ge$) some value $A$.

For example, say $n=10$.

The total number of possible combinations are $C=6^{10} \approx 60.5\text{ million}$.

One way to find a string which averages more than say $A=4$ is to brute force through the $60.5$ millions strings and compute the average of each string to check if it is greater than $A$. Also, average is just an example, eventually average can be any other function on the selected digits.

But this to me seems like a rather poor method which gets intractable pretty soon. Is there any other way?

Any help and potential directions will helps. Thanks!

EDIT:

So I ended up doing this as a solution

Construct a tree from the different digits. For exampe if the possible set of digits are {1,2} then a 3 level tree would look somethigns like this.

                            root
                         /        \
                        1          2
                    /      \    /     \
                   1       2    1     2
                 /  \    /  \  /  \  /  \
                1   2   1   2  1  2  1   2

Each path to the leaf of the tree is a combination. By traversing each path and computing the average at the leaf, a particular combination can be validated.

222 - avg 2.000000 > 1.500000 -> include in acceptable set
221 - avg 1.666667 > 1.500000 -> include in acceptable set
212 - avg 1.666667 > 1.500000 -> include in acceptable set
211 - avg 1.333333 < 1.500000 -> adding 1 and below to the exclude list
122 - avg 1.666667 > 1.500000 -> include in acceptable set
121 - avg 1.333333 < 1.500000 -> skipping this vote combo
112 - avg 1.333333 < 1.500000 -> skipping this vote combo
111 - avg 1.000000 < 1.500000 -> skipping this vote combo

Thus we have all 3 digit combinations of {1,2} with satisfy the threshold criterion of 1.5. Now while traversing through the tree first three combinations {222,221,212} are valid. 211 is not valid, so the last 1 is added to another list called excluded list {1}. 122 is valid. 121 is not valid, however 1 is already present in excluded list so not added. 112 is not valid, an now 2 is also added to the excluded list. Now the excluded list contain both 1 and 2 and so the program is terminated. So the solution is to traverse the tree is in right first pre-order traversal computing the average every time and if the threshold criterion is not satified then the last digit is added to the excluded list. The terminating condition is when all digits are present in the excluded list.

EDIT 2:

Although the above solution "works", it is not viable since it is ploynomial time in $O(m^n)$. For n=20 it tool about 10 secs, however for n=30 it took close to 5.5 hrs. This problem can of course be parallelized, however I have not given it a try. I am still looking for algorithmic solutions in less than or equal to log-linear time.

$\endgroup$
  • 1
    $\begingroup$ One thing about "average" is that order doesn't matter, and that could reduce the computational challenge considerably. When you say "It's just an example," and in general you want to be able to handle any function on the selected digits, it's going to be tough to give a general answer for how to do better than brute force. Doing better requires knowing something about the function. $\endgroup$ – StumpyLeg Jun 20 '14 at 20:09
  • $\begingroup$ Thanks. How about for now we assume that the function is Average - how to reduce the computational complexity then? $\endgroup$ – Manas Jun 20 '14 at 20:40
  • 1
    $\begingroup$ "This criterion is" or "These criteria are". (I did a grammatical correction, including the one in the subject line.) $\endgroup$ – Michael Hardy Jul 1 '14 at 17:44
1
$\begingroup$

To get approximate values (in some cases, exact) one procedure is to convert the counting to a probabilistic experiment: in our case, imagine that all string of length $n$ are equiprobable and we pick one of the at random. What is the probability that is fulfills the restriction $ \frac{1}{n}\sum x_i \ge A$ ?

Now, each $x_i$ is a discrete uniform in $1 \cdots 6$, with mean $3.5$, variance $(6^2-1)/12=35/12$ The sum of $n$ such variables will follow, for large $n$, approximately a normal distribution (CLT), and then we can compute the probabilty that that variable exceeds $nA$ (Gaussian integral).

Then the desired count can be approximated as $C \approx P \, 6^n$. For this approximation to be useful, we'd expect that the above probability is neither too small or too big; otherwise, we should try other approximations.

$\endgroup$
0
$\begingroup$

In response to the follow-up comment, focusing on "average":

Since order doesn't matter, we can imagine putting all the digits in increasing order. So, all the 1's first, then the 2's, etc. Then there are only five increments to worry about, namely when we hop from 1 to 2, then from 2 to 3, ... and finally from 5 to 6.

Now we imagine the ten digits laid out in order before us, and we have to place "hop tokens" between them. A hop token between digits three and four means that digit four will be higher than digit three by at least 1. Two hop tokens in one slot means an increment of 2 between digits.

A hop token before the first digit means we skip right past 1 and start with 2. A hop token after the last digit means we never get to 6.

So...we have 11 possible slots for the hop tokens, and there are 5 tokens, which means we have no more than $11^5=161,051$ possibilities to worry about. And really it should even be a lot less than that, because the tokens are indistinguishable. But dividing by $5!$ yields a fraction, which means it's not quite that simple. I haven't figured out the right way to account for the indistinguishability. But you get the idea.

I'm pretty sure that in the end there will be a fairly simple calculation based on the properties of an 11-nomial distribution of the five hop tokens, if that makes sense.

Sorry for the long and not-entirely-conclusive response. I think it's too long to post as a comment.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.