@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]
....
  • Вопрос задан
  • 10192 просмотра
Решения вопроса 1
sergiks
@sergiks Куратор тега JavaScript
♬♬
Рекурсивный алгоритм:
  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"]]
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 3
longclaps
@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)
}
Ответ написан
@agaliullin
CEO & Founder of Futureinapps, LLC
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));

Первоисточник
Ответ написан
Комментировать
@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']));
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы