9
\$\begingroup\$

SPECIFICATION

Given m variables, create every combination up to order n. For example,

The output of mapping two variables (a and b) to order 1 would be:

  • a
  • b
  • a b

The output of mapping two variables (a and b) to order 2 would be:

  • a
  • a2
  • b
  • b2
  • a b
  • a2 b
  • a b2
  • a2 b2

The output of mapping two variables (a and b) to order 3 would be:

  • a
  • a2
  • a3
  • b
  • b2
  • b3
  • a b
  • a2 b
  • a3 b
  • a3 b2
  • a b2
  • a b3
  • a2 b3
  • a2 b2
  • a3 b3

The output of mapping three variables (a, b, and c) to order 1 would be:

  • a
  • b
  • c
  • a b
  • b c
  • a c
  • a b c

The output of mapping m variables to order n would be:

  • etc.

WINNING CRITERIA

Output every possible combination as outlined above. Order does not matter. Where in your code you print to the screen does not matter. All that matters is that what shows up in your output is correct.

\$\endgroup\$
  • 1
    \$\begingroup\$ How are we intended to output? Should we use ^? \$\endgroup\$ – Wheat Wizard Mar 10 '17 at 22:08
  • 1
    \$\begingroup\$ Can we raise things to the zero or one (e.g. a^1) \$\endgroup\$ – Wheat Wizard Mar 10 '17 at 22:08
  • 1
    \$\begingroup\$ What if m is greater than 26? do we have to support values that high? \$\endgroup\$ – Wheat Wizard Mar 10 '17 at 22:11
  • 1
    \$\begingroup\$ @user1873073 the problem isn't the maximum order but the maximum number of variable names. \$\endgroup\$ – Martin Ender Mar 10 '17 at 22:24
  • 1
    \$\begingroup\$ How will the variables be given? many of the comments assume the input will be a number of variables, but the text given m variables implies a list of variables will be given. If only the number of variables is given and 0,1,2,3..27,28,29 raised to powers ^0,^1,^2 etc is acceptable output (as I am inferring from your last comment) it makes things easier. \$\endgroup\$ – Level River St Mar 10 '17 at 23:09

11 Answers 11

4
\$\begingroup\$

Brachylog, 6 bytes

j₎o⊇ᵘb

Takes input as a couple, containing the list of variables and the order. Output is a list of lists of variables, where powers are represented by repeated variables. (e.g. "a²b" is ["a","a","b"])

Try it online!

j₎ joins the first input with itself as many times as stated by the second input. o orders the list obtained, and then ⊇ᵘ finds all unique subsets of that ordered list. Finally, we remove the first element with b, since this will always be the empty answer, which is not contemplated by the challenge.

\$\endgroup\$
14
\$\begingroup\$

LATEX, 354 bytes

When I saw this I knew it had to be done in Latex. Equations just look so crisp and clean in Latex and I can't stand using ^ for power.

\documentclass{article}\input tikz\usepackage{intcalc}\usepackage{ifthen}\begin{document}\typein[\a]{}\typein[\b]{}\foreach\x in{1,...,\intcalcPow{\b+1}{\a}}{\begin{equation}\foreach[count=\i]\y in{a,...,z}{\ifthenelse{\(\i<\a\)\OR\(\i=\a\)}{\y^\intcalcDiv{\intcalcMod{\x}{\intcalcPow{\b+1}{\i}}}{\intcalcPow{\b+1}{\i-1}}}{}}\end{equation}}\end{document}

Explanation

There are three main forces at work here \typein which is what allows us to take input from the command line, the intcalc package which is what allows us to make calculations with our variables, and the Latexequation environment.


Once we have taken in input we begin a loop we loop \intcalcPow{\b+1}{\a} times, once for each result we want to print. Each loop we begin an equation environment and loop through the alphabet keeping track of \y for the current letter and \i for the current number of runs. If \i is greater than or equal to \a we don't print anything at all (according to the specs this is not strictly necessary however Latex will overflow for values greater than 1 if we don't do this). We then print \y to our equation and raise it to the power of

\intcalcDiv{\intcalcMod{\x}{\intcalcPow{\b+1}{\i}}}{\intcalcPow{\b+1}{\i-1}}

That whole mess simply means take the \ith digit of \x in base \b+1. This ensures that the powers are decoded properly.

Example output:

Here is the output for 3, 2

Output

\$\endgroup\$
  • 1
    \$\begingroup\$ Note that your output includes a^0 b^0 c^0 = 1, while the test cases do not. That being said, I think you're right and the test cases are wrong :) \$\endgroup\$ – Greg Martin Mar 11 '17 at 1:28
  • \$\begingroup\$ @GregMartin Yes, mathematically speaking the empty set should be in the en.wikipedia.org/wiki/Power_set \$\endgroup\$ – Karl Napf Mar 11 '17 at 4:45
  • \$\begingroup\$ @KarlNapf An expression equal to 1 is not the empty set. Nor is a tuple containing 3 zeros. \$\endgroup\$ – jpmc26 Mar 11 '17 at 10:23
  • \$\begingroup\$ @jpmc26 Yes, not in the specification of this golf. It is like the powerset of (for n=3) {a,a,a,b,b,b,c,c,c} without the empty set \$\endgroup\$ – Karl Napf Mar 12 '17 at 15:59
  • \$\begingroup\$ @KarlNapf It's mathematically not the same. There is no empty set involved here. The challenge involves generating a set of tuples of specified length. \$\endgroup\$ – jpmc26 Mar 12 '17 at 22:14
5
\$\begingroup\$

Mathematica, 51 50 bytes

Rest[1##&@@@PowerRange[1,#^#2,#]~Distribute~List]&

Assumes "given m variables" means the first input is a list of variables.

If first input is an integer, 69 bytes

Rest[1##&@@@PowerRange[v=Unique[]~Table~#;1,v^#2,v]~Distribute~List]&

The variables are in the form $<integer> (e.g. $5)

\$\endgroup\$
  • \$\begingroup\$ TIL PowerRange is a thing! I agree with the interpretation of your first submission btw \$\endgroup\$ – Greg Martin Mar 11 '17 at 0:30
4
\$\begingroup\$

Haskell, 71 58 54 53 bytes

n#m=tail$concat<$>mapM(\x->(\i->x<$[1..i])<$>[0..n])m

Returns a list of strings and uses the output format "aabbb" for "a^2 b^3".

Usage example: 3 # "ab" -> ["b","bb","bbb","a","ab","abb","abbb","aa","aab","aabb","aabbb","aaa","aaab","aaabb","aaabbb"]. Try it online!.

Many bytes are spent for output formatting. A more flexible output, e.g. pairs of (variable, power) -> [('a',2),('b',3),('c',1)] for "a^2 b^3 c^1" would save a lot.

How it works

    mapM(\x->    )m      -- for each variable x in the input list m
      \i->x<$[1..i]      -- make i copies of x
             <$>[0..n]   -- for all numbers from 0 to n
                         -- in fact mapM makes all possible combinations hereof, i.e.
                         -- [["",""], ["", "b"], ["", "bb"] ... ["a",""], ["a","b"], ...]
  concat<$>              -- join all inner lists 
                         --    e.g ["aa","bbb"]  -> "aabbb"
tail                     -- drop the first (all powers = ^0)

With maximum flexibility, i.e. output format as (variable, power) pairs and including all-zero powers ("a^0 b^0 c^0") it boils down to

Haskell, 25 bytes:

f n=mapM((<$>[0..n]).(,))

Usage example: f 2 "ab":

[[('a',0),('b',0)],
 [('a',0),('b',1)],
 [('a',0),('b',2)],
 [('a',1),('b',0)],
 [('a',1),('b',1)],
 [('a',1),('b',2)],
 [('a',2),('b',0)],
 [('a',2),('b',1)],
 [('a',2),('b',2)]]

Dropping all-zero powers costs 5 bytes for a total of 30: f n=tail.mapM((<$>[0..n]).(,)).

\$\endgroup\$
  • \$\begingroup\$ For your second code, [('a',0),('b',0)] should not be in the output... \$\endgroup\$ – JungHwan Min Mar 11 '17 at 4:39
  • \$\begingroup\$ @JungHwanMin: my 25-byte solution is not meant to be an answer. It's a note to show that the combinatoric part of the challenge needs the least number of bytes - at least in Haskell. Dropping a^0 b^0 costs 5 bytes. I'll add another note. \$\endgroup\$ – nimi Mar 11 '17 at 13:03
4
\$\begingroup\$

Jelly, 20 17 bytes

ṗj€“”Ṣ€
ŒPçЀj“”Q

A dyadic link (function) that accepts a list of variable names* and the maximal order (an integer) and returns a list where each entry is a fully expanded representation of the multiplication (e.g. foo0bar3bof2 would be ['bar', 'bar', 'bar', 'bof', 'bof'].

* the variable names may be a string of unique characters (strings become lists of characters).

Try it online! - the footer calls the link as a dyad and then separates the resulting list of lists by line feeds and each entry by spaces for ease of reading.

Note: includes the 0 order (empty product) a dequeue, , may be inserted here ...ŒPḊç... to avoid that.

How?

ṗj€“”Ṣ€ - Link 1, sorted results of a Cartesian power: elements, power
ṗ       - Cartesian power of elements with given power
 j€“”   - join €ach with "" (flatten each by one level)
     Ṣ€ - sort €ach

ŒPçЀj“”Q - Main link: variableNames, maximalOrder
ŒP        - power-set of variableNames (e.g for ['a','b','c'] this would be ['','a','b','c','ab','ac','bc','abc'])
   Ѐ     - for €ach mapped over right argument (i.e. over the range [1,2,...,maximalOrder])
  ç       -     call the last link (1) as a dyad (i.e. power-set results are the elements and one of the range values is the power)
     j“”  - join with "" (flatten by one level)
        Q - unique values

13 byte version that will only work for a single string of unique characters (or a list of unique characters):

ŒPṗЀj“”F€Ṣ€Q

try it

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES proposal), 142 bytes

f=
(v,n)=>[...Array(++v**n)].map((_,i)=>i.toString(v).padStart(n,0).replace(/./g,(c,j)=>(+c?(10+j).toString(36):``)+(c>1?c.sup():``))).join`<br>`
<div oninput=o.innerHTML=f(v.value,n.value)><input id=v type=number min=1 value=1><input id=n type=number min=1 value=1><span id=o><br>a

Requires a browser with both ** and padStart support, so try Firefox 52 or Chrome 57.

\$\endgroup\$
3
\$\begingroup\$

Mathematica 100 bytes

Surely there is a more efficient way to accomplish this!

Two variables to order 4:

(Times@@@(MapThread[Power,#]&/@Outer[List,{Alphabet[][[1;;#]]},Rest@Tuples[Range[0,#2],#],1][[1]])) &

picture

\$\endgroup\$
3
\$\begingroup\$

Bash + sed, 60

A different, shorter approach to my previous answer.

Input as command-line parameters - m is given as a comma-separated list of variable names, and n as an integer:

p=eval\ printf
$p -vc %s {$1}^\\{0..$2}
$p '%s\\n' $c|sed 1d

Try it online.


Previous Answer:

Bash + coreutils, 91

Welcome to eval-escape-brace hell. Sometimes shell-script really gives just the right tool for the job. This is not the case here, but it works.

Input as command-line parameters - m is given as a comma-separated list of variable names, and n as an integer. Output is written out longhand - e.g. a^2 is actually written aa. This is acceptable as per this comment.

p=eval\ printf
$p -vc {%$[$2-1]s}
$p '%s\\n' $($p %s \{{$1}${c// /,}\\\,})|tr -d {}|sort -u

There may be shorter ways to do this.

Try it online.

Explanation

  • printf -vc {%$[$2-1]s} assigns the variable c to a string like { }, where the number of spaces is the order n - 1, so if n = 1, the result is {}, if n = 2, the result is { }, etc.
  • ${a[$1]} uses m as an index to the array a, so if m is 3, then the result is c
  • \{{a..${a[$1]}}${c// /,}\\,} is a multi-part brace expansion:
    • \{ - a literal {
    • {$1} is a is the brace expansion of the list m, e.g. {a,b,c} or a b c
    • ${c// /,} replaces the spaces in $c with commas, e.g. {,,} for n = 3, which is also a brace expansion which effectively repeats each element of {a..c} n times
    • \\\,} - a literal ,}
  • So for m = "a,b" and n = 2, this expands to {a,} {a,} {b,} {b,}
  • The inner printf removes the spaces to give {a,}{a,}{b,}{b,}, which itself is a brace expansion
  • This expands to aabb aab aab aa abb ab ab a abb ab ab a bb b b
  • The outer printf puts each of these elements on its own line
  • sort -u removes the duplicates
  • The tr -d {} is there to handle the case when n = 1. In this case the variable c will be {} which is not a brace expansion, but instead the literal characters are inserted. The tr removes them.

evals and \ escapes are placed very carefully to ensure that all the expansions occur in the necessary order.

\$\endgroup\$
3
\$\begingroup\$

Röda, 49 48 46 bytes

f n{r=[""]{|v|r=r...[seq(0,n)|[v.._]]}_;r[1:]}

Try it online!

I think it is correct. It doesn't use any separator between a variable and its order. The previous version used !, but I realized that it isn't strictly required.

Explained:

function f(n) {
    r := [""] /* r is a list with one empty string. */
    /* Loops over the variable names in the stream. */
    for var do
        /* Concatenates every element in r to */
        /* every element in the list that contains orders of */
        /* variable var. */
        r = r...[
            push(var..x) for x in [seq(0, n)]
        ]
    done
    r[1:] /* Return elements of r not counting the first. */
}
\$\endgroup\$
1
\$\begingroup\$

Python, 112 bytes

import itertools as t
f=lambda n,v:[''.join(map(str.__mul__,v,I))for I in t.product(range(n),repeat=len(v))][1:]

Usage:

for x in f(3, 'ab'):
    print(x)

Output:

b
bb
a
ab
abb
aa
aab
aabb

Nicer format in 115 bytes:

import itertools as t
f=lambda n,v:[''.join(map('{}^{}'.format,v,I))for I in t.product(range(n),repeat=len(v))][1:]

Output (same usage):

a^0b^1
a^0b^2
a^1b^0
a^1b^1
a^1b^2
a^2b^0
a^2b^1
a^2b^2

Even nicer in 125 bytes:

import itertools as t
f=lambda n,v:[''.join(c+'^%s'%i for c,i in zip(v,I)if i)for I in t.product(range(n),repeat=len(v))][1:]

Output:

b^1
b^2
a^1
a^1b^1
a^1b^2
a^2
a^2b^1
a^2b^2

The last 4 bytes ([1:]) in all are for removing the empty product.

These work in both Python 2 and 3.

\$\endgroup\$
0
\$\begingroup\$

C++14, 146 140 bytes

-6 byte for simpler output format.

Unnamed lambda, assuming input s like std::string and o as std::ostream:

[](auto s,int n,auto&o){int l=s.size(),k,c,*p=new int[l]{1};while(!c){for(c=1,k=0;k<l;o<<s[k]<<"^"<<p[k],p[k++]*=!(c=(p[k]+=c)>n));o<<" ";}}

Usage and explanation:

#include<iostream>
#include<string>

auto f=
[](auto s, int n, auto&o){
 int l=s.size(),              //string length
     k,                       //running variable for l
     c,                       //carry for the increment
    *p=new int[l]{1};         //init array with first elem 1
 while(!c){                   //if carry was leftover, break
  for(
   k=0,c=1;                   //always start with carry                  
   k<l;                       
    o<<s[k]<<"^"<<p[k],       //output
    p[k++]*=!(c=(p[k]+=c)>n)  
//               p[k]+=c      //inc p[k]  
//            c=(p[k]+=c)>n   //if value is greater than order  
//  p[k++]*=!(c=(p[k]+=c)>n)  //set p[k] to 0 and inc k
  );
  o<<" ";                     
 }
}
;

main(){
 f(std::string("ab"),3,std::cout);
 std::cout << "\n";
 f(std::string("abc"),2,std::cout);
}

Output:

a^1b^0 a^2b^0 a^3b^0 a^0b^1 a^1b^1 a^2b^1 a^3b^1 a^0b^2 a^1b^2 a^2b^2 a^3b^2 a^0b^3 a^1b^3 a^2b^3 a^3b^3 
a^1b^0c^0 a^0b^1c^0 a^1b^1c^0 a^0b^0c^1 a^1b^0c^1 a^0b^1c^1 a^1b^1c^1 
\$\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.