Как составить все возможные комбинации?

Question

[ya_yshel_rabotati_v_teleg]

есть массив a,b,c,d
как получить ?
[a,b,c,b]
[a,b,d,c]
[a,c,b,d]
[a,c,d,b]
....

Answer 1

[Сергей Соколов]

Рекурсивный алгоритм:

1. На первой позиции должна побывать каждая из букв.
   
2. Выбрали первую – надо всеми возможными способами перебрать оставшиеся. Смотрим на задачу точно так же: из (n - 1) букв надо перебрать все варианты. Go to 1)
   

мопед – мой

function permut8(arr, prepend) {
  var i, version, el, result = [];
  prepend = prepend || [];
  if(arr.length === 1) return [arr];
  for( i=0; i<arr.length; i++) {
    if( arr.length === 2) {
      result.push( prepend.concat( [arr[i], arr[(i+1)%2]] ));
    } else {
      version = arr.slice();
      el = version.splice(i,1);
      result = result.concat( permut8( version, prepend.concat(el)));
    }
  }  
  return result;
}

var test = permut8( 'abcd'.split('') );
test.map( e=>e.join(' ')).join("\n")
/*
a b c d
a b d c
a c b d
a c d b
a d b c
a d c b
b a c d
b a d c
b c a d
b c d a
b d a c
b d c a
c a b d
c a d b
c b a d
c b d a
c d a b
c d b a
d a b c
d a c b
d b a c
d b c a
d c a b
d c b a
*/

Его минус в том, что он не учитывает значения элементов. Если встретятся повторяющиеся – создадутся дублирующиеся варианты. Например, из ["a", "a"] получим два одинаковых [["a", "a"], ["a", "a"]]

Нерекурсивный алгоритм.
longclaps говорит, давай, мол, напишем, чтобы корректно без повторов генерил и при повторяющихся элементах.

Использовал известный с 14 века нерекурсивный алгоритм индуса Нарайана Пандита. Из любого порядка в массиве генерится следующая итерация, учитывая лексикографический (по алфавиту) порядок сортировки.

Мопед – мой, мыт

function nextLexInPlace(arr){
  var i, a = -1, b = -1;
  for( i = 0; i < arr.length-1; i++) if(arr[i] < arr[1+i]) a = i;
  if( !~a) return; // no more permutations
  for( i = a + 1; i < arr.length; i++) if(arr[a] < arr[i]) b = i;
  swap(arr, a, b);
  a++;
  b = arr.length - 1;
  while( a < b) swap(arr, a++, b--);
  return true;
}

function swap( arr, a, b) {
  var xx = arr[a];
  arr[a] = arr[b];
  arr[b] = xx;
}

function allMutations( source) {
  var result = [], arr = source.slice();
  result.push( arr.sort().slice());
  while( nextLexInPlace(arr)) result.push(arr.slice());
  return result;
}

var test = ['a','c','c']; JSON.stringify( allMutations(test))
// [["a","c","c"],["c","a","c"],["c","c","a"]]

И тот же мопед, но

с генератором

function* permutator(arr) {
  var i, a, b;

  function swap( arr, a, b) {
		var xx = arr[a];
		arr[a] = arr[b];
		arr[b] = xx;
	}
  
  yield arr.slice();

  while(true) {
    a = -1, b = -1;
		for( i = 0; i < arr.length-1; i++) if(arr[i] < arr[1+i]) a = i;
		if( !~a) return;
		for( i = a + 1; i < arr.length; i++) if(arr[a] < arr[i]) b = i;
		swap(arr, a++, b);
		b = arr.length - 1;
		while( a < b) swap(arr, a++, b--);
		yield arr.slice();
  }
}

function allMutations( source) {
  var all = [], result, G = permutator(source.slice().sort());
  while(true) {
    result = G.next();
    if(result.done) break;
    all.push( result.value);
  }
  return all;
}

var test = ['a','c','c']; JSON.stringify( allMutations(test))
// [["a","c","c"],["c","a","c"],["c","c","a"]]

Answer 2

[longclaps]

гугл

Сергей Соколов сказал, что мопед надо помыть

function* permutation(s) {
    if (s.length < 3) {
        yield s;
        if (s.length == 2) yield s[1] + s[0];
    } else {
        for (let i = 0; i < s.length; i++) {
            let h = s[i];
            for (let t of permutation(s.substr(0, i) +
                s.substr(i + 1))) yield h + t;
        }
    }
}

for (let s of permutation("abcd")) {
    console.log(s)
}

Comments

[Сергей Соколов]

это отрицает потенциальную полезность Тостера! : )

[longclaps]

Я исправился, Сергей Соколов!

[Сергей Соколов]

longclaps, супер!
Генераторы - это модно, спортивно, современно!

[longclaps]

Сергей Соколов, брошу-ка я тебе перчатку:
Допустим, на входе "adcc", тогда на выходе будут дублирующиеся строки.
Сделай так, чтобы этого не было, но не накапливая выхлоп в качестве фильтра (ведь он может быть огромным!)
В общем, помой мопед )
Я тоже напишу к концу дня.

[Сергей Соколов]

longclaps, надеюсь, не

металлическую )

Можно входной массив просто сортировать и уникалить перед всей обработкой.
upd. а, не..

[longclaps]

Сергей Соколов,

function* permutation(s) {
    if (s.length < 3) {
        yield s;
        if (s.length == 2) yield s[1] + s[0];
    } else {
        for (let i = 0; i < s.length; i++) {
            let h = s[i];
            for (let t of permutation(s.substr(0, i) +
                s.substr(i + 1))) yield h + t;
        }
    }
}

function* spread(s, i, cnt) {
    for (; i < s.length; i++) {
        let c = s[i];
        if (cnt[c] > 1) {
            let cn = Object.assign({}, cnt);
            cn[c]--;
            i++;
            for (let j = i; j <= s.length; j++) {
                for (let t of spread(s.substr(0, j)
                    + c + s.substr(j), i, cn)) yield t;
            }
            return
        }
    }
    yield s;
}

function* permUniq(s) {
    let cnt = {};
    for (let c of s) cnt[c] = (cnt[c] || 0) + 1;
    for (let t of permutation(''.concat(...new Set(s)))) {
        for (let u of spread(t, 0, cnt)) {
            yield u
        }
    }
}

for (let s of ["aaa", "aab", "abc", "aabb",
    "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"]) {
    for (let t of permUniq(s)) console.log(t);
    console.log("~~~~");
}

[Сергей Соколов]

longclaps, уж с генератором точно алгоритм Нарайана надо бы! У меня с вашими тестами

получилось так

/*
[
[["a","a","a"]],
[["a","a","b"],["a","b","a"],["b","a","a"]],
[["a","b","c"],["a","c","b"],["b","a","c"],["b","c","a"],["c","a","b"],["c","b","a"]],
[["a","a","b","b"],["a","b","a","b"],["a","b","b","a"],["b","a","a","b"],["b","a","b","a"],["b","b","a","a"]],
[["a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a","a"]]
]
*/

[longclaps]

Сергей Соколов, про Нарайана знал, но не разбирался, попозже помедитирую.

Answer 3

[Airat Galiullin]

let swap = function (array, pos1, pos2) {
    var temp = array[pos1];
    array[pos1] = array[pos2];
    array[pos2] = temp;
};
let combinations = (array, output, n) => {
    n = n || array.length;
    if (n === 1) {
        output(array);
    } else {
        for (var i = 1; i <= n; i += 1) {
        combinations(array, output, n - 1);
        if (n % 2) {
            var j = 1;
        } else {
            var j = i;
        }
        swap(array, j - 1, n - 1); 
    }
}
};
combinations(['a', 'b', 'c', ], (result)=>console.log(result));

Первоисточник

Answer 4

[Ridz]

если все элементы в массиве разные

function fn(e) {
    for (var g = [], b = e.length, h = Math.pow(b, b - 2);; h++) {
        var d = h.toString(b),
            c = d.length;
            if (c > b) break;
            c < b && (d = 0 + d);
            var f = "";
            for (c = 0; c < b; c++) a = parseInt(d[c], b), f += e[a];
            e.every(function(b) {
                return 0 <= f.indexOf(b)
            }) && g.push(f)

    }
    return g
};
console.log(fn(['a','b','c','d']));