Рекурсивно объединить массив с помощью JS/Coffeescript

Несколько идиоматическое решение CoffeeScript:

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]

Затем allHints(12) возвращает ['a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l', ';', 'aa', 'as'].

Первый знак (...) преобразует двумерный массив, созданный вложенными включениями, в список аргументов одномерного массива для concat().

Это решение, очевидно, не очень эффективно, поскольку оно генерирует все перестановки только для того, чтобы отбросить ненужные.

Похоже, вам в основном нужен дважды вложенный цикл, в котором вы перебираете каждый символ каждый раз, когда вы перебираете каждый символ, и в этом случае вы могли бы также использовать длину массива HINTS и не беспокоиться о подсчете вещей самостоятельно.

Как это?

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;
}

Это не рекурсия, но рекурсия здесь все равно не поможет. Это также дает желаемый результат, который вы описали, но без каких-либо произвольных ограничений на длину. Если вы хотите ограничить результат, вы можете определить все подсказки следующим образом:

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);
}

Тогда allhints(4) просто возвращает ["a", "s", "d", "f"].

Проблема, которую вы действительно хотите решить, заключается в том, «как я могу сгенерировать все подмножества набора», в частности, «как мне сгенерировать все подмножества с учетом массива HINTS».

Самый простой способ сделать это — принять во внимание, что каждый элемент в вашем наборе может быть отображен в двоичную строку. Ваш массив HINTS состоит из 10 элементов, поэтому, чтобы найти все подмножества, нам просто нужно посчитать от 0000000000 до 1111111111 в двоичном формате, а затем выбрать любые элементы по мере продвижения (например, 0000000101 будет «k;»).

Приведенный ниже код почти завершен; Я взглянул на него и, кажется, есть ошибка (позже посмотрю, смогу ли я ее отладить).

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);

Проблема, похоже, действительно заключается в создании множества возможных подмножеств данного множества. который иногда называют набором мощности набора.

В основном есть 3 возможных решения: 1) Биномиальные коэффициенты. См. http://en.wikipedia.org/wiki/Binomial_coefficient. Реализацию можно найти в Pyton. itertools. Биномиальные коэффициенты дают вам подмножества определенной длины. Если вы объедините подмножества от длины 0 до длины вашего исходного набора, вы закончите.

2) Рекурсивный алгоритм, который «выращивает» подмножества в поколениях. Смотрите ответ Киото. См. мою более подробную версию ниже. В статье в Википедии упоминается треугольник Паскаля, который является подсказкой для такого алгоритма.

3) Элемент находится в подмножестве или нет. Это означает, что существует 2 ^ (длина набора) подмножеств. Каждое подмножество может быть закодировано как двоичное число с длиной цифр подмножества. это делается в ответе NT3RP. Вы также можете использовать для этого массив логических значений вместо строки. Я размещаю свою версию С# ниже.

Моя рекурсивная версия Powerset в coffeescript на основе реализации в Миранде. (Мне было интересно, смогу ли я закодировать его в Coffeescript так же компактно, как в Миранде, и тогда я нашел этот вопрос)

powerset в Миранде

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

powerset в кофескрипте:

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

Мои интересы во всем этом:

Некоторое время назад я написал реализацию подхода двоичных чисел для создания подмножеств на C#. Ради интереса я также хотел написать версию, которая «выращивает» подмножества.

Я знал Миранду, очень лаконичный функциональный язык программирования. Мне было интересно, позволяет ли coffeescript тот же уровень, что и succinctnes. Мне не удалось добиться этого в Scala, F # или Clojure. Я не смог сделать это в coffeescript, но "киото" показал, как это делается.

Ниже версии C# как IEnumerable. Он генерирует кортежи элементов, которые находятся в подмножестве и всех остальных элементах.

...
//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;
}
...

Простое решение:

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

Это можно оптимизировать, чтобы не искать базовый символ каждый раз с помощью вложенного цикла, но для ясности оставляем как есть.