Number of unique outputs by substituting variables

9

1

Given a set of formulas like this:

bacb
bcab
cbba
abbc

Give an algorithm that finds the number of unique results you can get when each variable is substituted for either "0" or "1" in every formula.

There are (k!)^2 formulas, each with 2k-1 variables and k^2 terms. Express your asymptotics in terms of k.

Fastest algorithm wins. In case of a tie the solution with lower asymptotic memory usage wins. If that's still a tie, first post wins.

For the example above the following results can be acquired by substituting the variables:

1110, 0110, 1001, 0100, 1000, 0000, 0010, 1101, 1111, 0001, 1011, 0111

So the correct answer is 12. Among others, 1010 can not be made using the above formulas.

I've made three more tests cases, with respective solutions of 230, 12076 and 1446672.

orlp

Posted 2015-04-11T19:10:45.610

Reputation: 37 067

Clarification: what is k in the question? Is it just some abstract constant? – isaacg – 2015-04-11T19:48:45.840

@isaacg Yes. It's to prevent ties between solutions that are faster for less but larger formulas, for example. – orlp – 2015-04-11T19:49:30.827

So each letter a,b,... is a variable? And we have always only an uneven number of variables? Doesn't it matter how long the sequence of variables is, and on how many formulas you are given? – flawr – 2015-04-11T20:18:02.907

@flawr The exact relation between the number of variables, number of terms and number of formulas is given in the question. – orlp – 2015-04-11T20:19:42.010

Does 'can be' mean that you can get up to $(k!)^2$ formulas or are there exactly $(k!)^2$ formulas? Besides that, do you have any application for an algorithm with those specifications? I'm just asking because the specs seem to be pretty arbitrary. – flawr – 2015-04-11T20:31:58.300

@flawr The figures are exact, I just meant that it could be for any positive integer $k$. And this is a subproblem I encountered while making an answer to this challenge, that I thought was interesting on its own.

– orlp – 2015-04-11T20:33:38.233

This is a cool challenge. It took me a while to understand that the formulæ represent numbers. – FUZxxl – 2015-04-11T20:46:23.730

I'm confused. What are the formulas? What are variables and terms? – xnor – 2015-04-11T20:59:48.637

@xnor In the example above there are 4 formulas (bacb, bcab, cbba, abbc). The first formula (bacb) has 4 terms, in order: b, a, c, b. All formulas have 3 variables, a, b, and c. – orlp – 2015-04-11T21:07:44.730

@orlp I see now, thanks. I believe counting 3-colorings reduces to this. So it's #P-hard. There won't be a polynomial time solution, thought different exponential ones can still compete. – xnor – 2015-04-11T21:25:45.237

Answers

2

Mathematica, O(k^2(k!)^2) time

Length[Union@@(Fold[Flatten[{StringReplace[#,#2->"0"],StringReplace[#,#2->"1"]}]&,#,Union[Characters[#]]]&/@#)]&

Hopefully I calculated the time complexity correctly. Input is a list of formulas such as {"bacb","bcab","cbba","abbc"}. Runs in less than 30 seconds for every test case on my machine, but who cares about absolute times?

Explanation:

  • First off, the & at the end makes it a pure function, with # referring to the first argument, #2 being the second argument, etc.
  • Length[*..*] takes the length of the list contained inside it.
  • Union@@(*..*) takes the contained list and supplies it as the arguments for Union, which returns a list of the unique elements in any of its arguments.
  • *..*&/@# takes a pure function and maps it over the list of formulas, so that {a,b,c} becomes {f[a],f[b],f[c]}. Note that in nested pure functions, #n refers to its innermost arguments.
  • Fold[*..*&,#,*..*] takes a accumulator function, starting value, and list, and returns f[f[...[f[starting value,l_1],l_2],...],l_n].
  • Union[Characters[#]] takes all the characters in the current formula and gets all the unique elements, giving us the variables.
  • Flatten[*..*] flattens its argument, so that {{{a},b},{{c,{d}}}} becomes {a,b,c,d}.
  • {*..*,*..*} is simply a way to combine the two results using the above Flatten.
  • StringReplace[#,#2->"0/1"] takes the previous result and returns it with the current variable replaced with either 0 or 1.

LegionMammal978

Posted 2015-04-11T19:10:45.610

Reputation: 15 731

Why are you using k as the variable in your time? Still, factorial time! Phew! – theonlygusti – 2015-04-13T18:33:16.127

The op said: "Express your asymptotics in terms of k." Also, I had to do a GeneralUtilities\Benchmark` for each method used. – LegionMammal978 – 2015-04-13T18:57:39.660

Care to add a plain english description of your algorithm? I'm unfamiliar with Mathematica, so I can't verify your solution. – orlp – 2015-04-17T01:46:48.873

Asked: 2015-04-11T19:10:45.610

Viewed: 226 times

Active: 2016-07-06T13:24:34.790