Recursively Concatenate Array with JS/Coffeescript

I'm trying to generate something similar to the following:

Given HINTS = ["a", "s", "d", "f", "g", "h", "j", "k", "l", ";"] then allHints(21) should give an array similar to:

["a", "s", "d", "f", "g", "h", "j", "k", "l", ";", "aa", "as", "ad", "af", "ag", "ah", "aj", "ak", "af"..."sa", "ss", "sd"...]

That is, all elements joined together one-by-one to make individual combinations. I'd like to write this using some sort of recursion, if possible, since it seems like a problem inclined to be solved that way.

My solution was to nest two for loops iterating through each combination by 9's (given that's how many hints there are) but it seems it gets stuck somewhere around the second time. I'm not too familiar with Coffeescripts for syntax but I've tried something similar to:

allHints = ->
  for i i开发者_开发问答n [0...anchors]
    do (i) ->
      if i > 9
        (for y in [0...i % 9]
          do (y) ->
                       #changing this to HINTS[Math.round(i / 10)] as it should be produces weird results
            HINTS[y] + HINTS[i % 9 - 1])[0]
      else
        HINTS[i]


console.log allHints 19

But unfortunately, that provides an undefined for the last element. Can anyone help me figure out how to the correct for loops to generate an array? Here's a gist for reference.

---

A somewhat idiomatic CoffeeScript solution:

HINTS = ["a", "s", "d", "f", "g", "h", "j", "k", "l", ";"]

allHints = (n) ->
  HINTS.concat(((b + a for a in HINTS) for b in HINTS)...)[0...n]

Then allHints(12) returns ['a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l', ';', 'aa', 'as'].

The first splat (...) converts the 2D array created by the nested comprehensions into a list of 1D array arguments for concat().

This solution is obviously not very efficient since it generates all permutations only to throw away any it doesn't need.

---

It sounds like you basically want a doubly nested loop where you iterate over each character each time you iterate over each character, in which case you might as well use the length of the HINTS array and not bother with counting stuff out yourself.

How's this?

var HINTS = ["a", "s", "d", "f", "g", "h", "j", "k", "l", ";"]

function allhints() {
  var all = Array(); // Create a new array
  all = all.concat(HINTS); // Add the individual hints
  for (var i=0; i<HINTS.length; i++) // for each character in HINTS
    for (var j=0; j<HINTS.length; j++) // with each character in HINTS
      all.push(HINTS[i] + HINTS[j]); // Append the two combined hint characters
  return all;
}

It's not recursive, but recursion doesn't really help here anyway. It also gives the desired outcome you described, but without any arbitrary limits to the length. If you do want to limit the result, you can define allhints like so:

function allhints(n) {
  var all = Array(); // Create a new array
  all = all.concat(HINTS); // Add the individual hints
  for (var i=0; i<HINTS.length; i++) // for each character in HINTS
    for (var j=0; j<HINTS.length && all.length < n; j++)  // with each character in HINTS
      all.push(HINTS[i] + HINTS[j]); // Append the two combined hint characters
  return all.slice(0,n);
}

So then allhints(4) just returns ["a", "s", "d", "f"].

---

The problem that you really seem to want solved is "how can I generate all subsets of a set", in particular, "how do I generate all subsets given the array HINTS".

The easiest way to do this is to consider that each element in your set can be mapped to a binary string. Your array, HINTS, has 10 elements, so to find all subsets, we just need to count from 0000000000 to 1111111111 in binary, then select whichever elements as we go (for example, 0000000101 would be "k;").

The below code is almost complete; I've taken a look at it and there seems to be a bug (I'll see if I can debug it later).

HINTS = ["a", "s", "d", "f", "g", "h", "j", "k", "l", ";"]

var results = [];
var binCounter;
var hint;
for ( var i = 0; i < Math.pow(2, HINTS.length); i++) {
    binCounter = i.toString(2); //convert the number to binary
    hint = "";

    //generate the hint
    for ( var j = 0; j < binCounter.length; j++) { 

        //if the boolean digit was true, pick the corresponding element from our set
        if (binCounter[j] == 1) {
            hint += HINTS[j];
        }
    } 
    results.push(hint);
}
console.log(results);

---

The problem seems indeed to be generating the set of possible subsets of a given set. which sometimes is referred to as the powerset of a set.

Basically there are 3 possible solutions: 1) Binomial coefficients. See http://en.wikipedia.org/wiki/Binomial_coefficient An implementation can be found in Pyton's itertools. Binomial coefficients give you subsets of a certain length. If you combine the subsets from length 0 upto the length of your original set you are done.

2) A recursive algorithm that "grows" subsets in generations. See kyoto's answer. See my more verbose version below.the wikipedia article mentions Pascal's triangle which is a hint for such an algorithm

3) An element is in a subset or not. This means there are 2^(length of the set) subsets. Each subset can be in encoded as a binary number with length of the subsets digits. this is done in NT3RP's answer. You could also use an array of booleans for this instead of a string. I post my C# version below.

My recursive version of Powerset in coffeescript based on an implementation in Miranda. (I was wondering whether I could code it in Coffeescript as compact as in Miranda and then I found this question)

powerset in Miranda

powerset []     = [[]]
powerset (x:xs) = [[x] ++ y | y <- ys] ++ ys
              where ys = powerset xs

powerset in coffeescript:

powerset = (zs) ->
  if zs.length is 0
    [[]]
else  
    [x,xs...]=zs
    ys=powerset xs
    result=([x].concat y for y in ys).concat ys

# number of elements in powerset is 2^length of the powerset

res=powerset [1,2,3,4,5,6,7,8,9,10]
console.log res
console.log "length:" +res.length

My interests in all this:

I wrote a C# implementation of the binary number approach for generating subsets a while ago. For fun I also wanted to write a version that "grows" the subsets.

I knew Miranda a very succinct functional programming language. I wondered whether coffeescript allowed the same level as succinctnes.I was not able to achieve this in Scala, F# or Clojure. I was not able to do it in coffeescript but "kyoto" showed how it is done.

Below the C# version as IEnumerable. It generates tuples of elements that are in the subset and all other elements.

...
//imports and house keeping removed
    private static IEnumerable<Tuple<IList<T>,IList<T>>> SubsetImpl<T>(this IList<T> argList){
 int elementCount=argList.Count; 
 int bits=(1<<elementCount);//2 to the power of elementCount
 List<Tuple<IList<T>,IList<T>>> subsets=new List<Tuple<IList<T>, IList<T>>>(bits);
 for(int i=0;i<bits;i++){
   int[] mask={i};          
   BitArray flags=new BitArray(mask);
    IList<T> incomb=new List<T>();
    IList<T> outcomb=new List<T>();     


   for(int j=0;j<argList.Count;j++){
    if( flags[j]){
      incomb.Add(argList[j]);               
    }else{
     outcomb.Add(argList[j]);
    }
   }
   Tuple<IList<T>,IList<T>> t=new Tuple<IList<T>,IList<T>>(incomb,outcomb);
   subsets.Add(t);
 }
 return subsets;
}
...

---

A simple solution:

allHints = (n) ->
    ln = hints.length

    # return sliced array if n is less than it's length
    return hints.slice(0, n) if n <= ln

    # clone the array, find number of possible combinations
    clone = hints.slice()
    limit = Math.min(n, ln*ln)

    # add the combinations up to the requested length or limit
    for i in [ln...limit]
        clone[i] = hints[Math.floor(i / ln) - 1] + hints[i % ln]

    return clone

This could be optimized to not lookup the base character everytime with a nested loop, but is left as is for clarity.