Две комбинации элементов массива javascript

Если у меня есть массив букв, например

['A','C','D','E']

и я хотел найти все 2-х буквенные комбинации этого массива, что лучший способ сделать это, не используя 2 для циклов. Например:

for (var i=0; i<arr.length;i++) {
  for (var j=i+1; j<arr.length;j++) {
    console.log(arr[i] + " " + arr[j]);
  }
}

Проблема в том, что если массив становится массивным (1000 элементов), он обычно истекает. Есть ли другой способ (альтернативная структура данных и т. Д.)?

javascript,arrays,algorithm,data-structures,ecmascript-6,

0

Ответов: 4

2

Использовать .map()

Что-то вроде этого

var arr = ['A','C','D','E'],
    combinations = arr.map((v,i)=>arr.slice(i+1).map(v2=>v+v2));

console.log(combinations);

Хотя этот код также будет повторяться дважды над элементами. ( он будет работать хуже, чем ваш код, поскольку mapвыполняет функцию для каждого элемента, а также создает временные копии массивов с помощью slice, поэтому он здесь только для альтернативного подхода, а не более результативный. )

1

Не только два, но и любое количество элементов, которые вы можете сделать следующим образом;

Array.prototype.combinations = function(n){
  return this.reduce((p,c,i,a) => p.concat(n > 1 ? a.slice(i+1).combinations(n-1).map(e => [].concat(e,c))
                                                 : [[c]]),[]);
};

console.log(JSON.stringify([1,2,3,4,5,6].combinations(2)));
console.log(JSON.stringify([1,2,3,4,5,6].combinations(3)));

Ну, по комментариям @Lucas Kot-Zaniewski, я переработал свой код для использования .push()операций вместо .concat()инструкций, а также там, где требуется операция распространения, которую я использовал Array.prototype.push.apply(context,[args]). Эти два изменения заставили код работать в 2,5 ~ 3 раза быстрее (в результате 3,5-7 мс против 9,5-19 мс), когда задан вход из массива из 100 элементов и запрошена комбинация из двух из них. И все же, однажды попробовав 1000 предметов из 2 комбинаций, разница более драматична, чем 400 мс против 6000 мс.

Тест можно увидеть на странице https://repl.it/DyrU

Array.prototype.combinations = function(n){
  return this.reduce((p,c,i,a) => (Array.prototype.push.apply(p,n > 1 ? a.slice(i+1).combinations(n-1).map(e => (e.push(c),e))
                                                                      : [[c]]),p),[]);
};

console.log(JSON.stringify([1,2,3,4,5,6].combinations(2)));

1

Я действительно избил это в землю. Как и ожидалось, ответ @Louis Durand двух вложенных циклов был самым быстрым в массиве, содержащем 100 строк (около 4 мс на моей машине). Это показывает, что вложенная петля, вероятно, является вашим лучшим выбором в этой ситуации.

Второй самый быстрый - это рекурсивное решение, которое делало то же самое около 7-8 мс.

В-третьих, это ответ @Redu, который за такую ??же задачу составлял около 12-15 мс. Я подозреваю, что его реализация медленнее, потому что он использует метод slice в своем algo для обновления массива (другие ответы только увеличивают индекс, оставляя неизменный входной массив, что намного быстрее). Также эта реализация приводит к тому, что несколько копий входного массива хранятся в памяти (каждый раз, когда вызываемая функция создает новый входной массив из исходного массива, из которого он удаляет первый элемент). Это также может повлиять на производительность.

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

    var arr = [];
    for (var i = 0; i< 100; i++){
        arr.push(i+"");
      }
 /*
    console.time("test0");
    test0();

    function test0() {
    var s = "";
    for (var i=0; i<arr.length-1;i++) {
      for (var j=i+1; j<arr.length;j++) {
        s += arr[i] + " " + arr[j]+" ; ";
      }
      s += "
";
    }

    console.log(s);
    }
    console.timeEnd("test0"); 
*/
   
    console.time("test1"); 
    test1();
    function test1() {
    var output = [];
    getCombos(0, 0, [], 2);
    console.log(JSON.stringify(output));

     function getCombos(index, depth, tmp, k){
     if(depth < k){
         for(var i = index; i<arr.length; i++){
             var tmp1 =  [arr[i]];
             Array.prototype.push.apply(tmp1, tmp);
             getCombos(i+1, depth+1,tmp1, k);
           }
        }else{
             output.push(tmp);
          }
        }
    }
    console.timeEnd("test1");

        /*
        console.time("test2"); 
        test2();
        function test2(){
    Array.prototype.combinations = function(n){
      return this.reduce((p,c,i,a) => (Array.prototype.push.apply(p,n > 1 ? a.slice(i+1).combinations(n-1).map(e => (e.push(c),e))
                                                                          : [[c]]),p),[]);

};

console.log(JSON.stringify(arr.combinations(2)));
    }

    console.timeEnd("test2");*/

Вот рекурсивное решение, которое не решает проблему сложности времени, но это еще один способ рассмотрения. Дополнительным преимуществом является то, что вы можете обобщить его на любой k, чтобы не застревать в поиске только двух букв. Также вы объявляете только один цикл (хотя более чем одна его копия будет существовать в вашем стеке вызовов)

var arr = ["a", "b", "c", "d", "e"];
var output = "";
getCombos(0, 0, [], 2);
console.log(output);

 function getCombos(index, depth, tmp, k){
 if(depth < k){
     for(var i = index; i<arr.length; i++){
         var tmp1 =  [...tmp, arr[i]];
         getCombos(i+1, depth+1,tmp1, k);
       }
    }else{
         output += tmp.toString() + ";";
      }
    }
0

Я думаю, что ваш код имеет здесь ошибку, E никогда не будет использоваться. Это должно быть:

var s = "";
for (var i=0; i<arr.length-1;i++) {
  for (var j=i+1; j<arr.length;j++) {
    s += arr[i] + " " + arr[j]+" ; ";
  }
  s += "
";
}
console.log(s);

Обратите внимание, что если вы регистрируете все в консоли, неудивительно, что это время.

JavaScript, массивы, алгоритм, структур данных, ECMAScript-6,
Похожие вопросы
Яндекс.Метрика