Получить перестановки под-массивов без изменения порядка под-массивов - PullRequest
Новая
       43

Получить перестановки под-массивов без изменения порядка под-массивов

0 голосов
/ 28 сентября 2018

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

  1. Если в какой-либо группе есть только одно слово, оно остается без изменений.(то есть ['cat'])
  2. Перестановка первой группы до завершения.
  3. Перестановка второй группы один раз, затем выполните шаг 1;только перестановка второй группы один раз каждый раз, когда выполняется шаг 1.
  4. Переставьте третью группу один раз, затем выполните шаг 2;только перестановка третьей группы один раз каждый раз, когда выполняется шаг 2.
  5. Продолжайте эту схему до тех пор, пока не будут созданы все группы.

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

function* permute(permutation) {
  const length = permutation.length;
  let c = Array(length).fill(0),
    i = 1,
    k, p;

  yield permutation;
  while (i < length) {
    if (c[i] < i) {
      k = (i % 2) ? c[i] : 0;
      p = permutation[i];
      permutation[i] = permutation[k];
      permutation[k] = p;
      ++c[i];
      i = 1;
      yield permutation;
    } else {
      c[i] = 0;
      ++i;
    }
  }
}
function* permuteGroups(input) {
  input.sort((a,b) => {return a.length-b.length;});
  let groups = [], //Holds the list of Generators and words
      groupsCache = [], //Copy of groups to reset the Generators
      g = 0, i = input.length, len = input[i - 1].length,
      gid = 0, currentGroup, currentSet, finished = [];

  //Helper function to reset a Generator
  function reset(gid) {
    groups[gid] = {
      'currentValue': undefined,
      'nextValue': undefined,
      'generator': permute(groupsCache[gid].split(',')),
      'gen2': permute(groupsCache[gid].split(','))
    };
    groups[gid].nextValue = groups[gid].gen2.next().value.join(',');
  }
  function fetch(gid, next) {
    if (!!next) {
      if (groups[gid].generator === undefined) return { 'currentValue': groups[gid].currentValue, 'nextValue': undefined };
      let cv = groups[gid].generator.next();
      let nv = groups[gid].gen2.next();
      cv = (cv.done) ? 'done' : ((cv.value) ? cv.value.join(',') : undefined);
      nv = (nv.done) ? 'done' : ((nv.value) ? nv.value.join(',') : undefined);
      groups[gid].currentValue = cv;
      groups[gid].nextValue = nv;
    }
    let output = {
      'currentValue': groups[gid].currentValue,
      'nextValue': groups[gid].nextValue
    };
    return output;
  }
  function getOutput(next) {
    let gid = 0, len = groups.length, output = [];
    while (gid < len) {
      output.push(fetch(gid++, next).currentValue);
    }
    return output;
  }

  //First move words into sub-arrays based on length
  groups.push([]);
  while (i--) {
    if (input[i].length == len) {
      groups[g].push(input[i]);
      continue;
    }
    groups[++g] = [input[i]];
    len = input[i].length;
  }
  groupsCache = groups.map(x => x.join(',')); // Convert each group into a string to preserve order
  //Turn the sub-arrays into Generators if they have more than one item
  len = groups.length - 1;
  while (i++ < len) {
    groups[i] = (groups[i].length > 1) ? { 'currentValue': undefined, 'nextValue': undefined, 'generator': permute(groups[i].toString().split(',')), 'gen2': permute(groups[i].toString().split(',')) } : { 'currentValue': groups[i].toString().split(','), 'nextValue': undefined, 'generator': undefined, 'gen2': undefined };
    if (groups[i].gen2) groups[i].nextValue = groups[i].gen2.next().value.join(',');
    finished[i] = (groups[i].nextValue) ? false : true;
  }
  //console.log(finished)

  //Yield initial output
  yield getOutput(true);

  let index = 0, isNotDone = true, isInc = false;
  while (isNotDone) {
    // If we're supposed to be going up to the next group, but there isn't one, reset the index back to zero
    // Fetch the next value for the current group...
    currentSet = fetch(index, true);
    /* default, default, default
     / "rabbit,beaver,calf,wolf,cat,fox,dog"
     * Flip [0], default, default
     / "beaver,rabbit,calf,wolf,cat,fox,dog"
     * Reset [0], flip [1], default
     / "rabbit,beaver,wolf,calf,cat,fox,dog"
     * Flip [0], flipped, default
     / "beaver,rabbit,wolf,calf,cat,fox,dog"
     * Reset [0], Reset [1], move [3]
     / "rabbit,beaver,calf,wolf,fox,cat,dog"
    */
    // and yield it.
    yield getOutput();
    // If this was the last value before this group is done...
    if (currentSet.nextValue == 'done') {
//       if (!groups[index+1] || finished.slice(index+1).every(x => x === true)) {
//         finished[index] = true;
//         console.log(finished)
//         if (finished.every(x => x === true)) {
//           isNotDone = false;
//         }
//         index = 0;
//         continue;
//       }
      // reset the current group
      reset(index);
      // and put it back on the first value
      fetch(index, true);
      // Move on to the next group
      index++;
      // Mark that we plan on going to the next group up
      isInc = true;
      continue;
    }
    // Otherwise if it is not the last value and the isInc flag is set
    if (isInc) {
      // Reset the index back to zero
      index = 0;
      isInc = false;
    }
  }
  return 'done';
}
let perm = permuteGroups(['dog','fox','cat','wolf','calf','beaver','rabbit']);
let result = perm.next();
while (!result.done) {
  console.log(result.value.toString());
  result = perm.next();
}

1 Ответ

0 голосов
/ 27 февраля 2019

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

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

function* permute(permutation) {
  const length = permutation.length;
  let c = Array(length).fill(0),
    i = 1, k;

  yield permutation;
  while (i < length) {
    if (c[i] < i) {
      k = (i % 2) ? c[i] : 0;
      [permutation[i], permutation[k]] = [permutation[k], permutation[i]];
      ++c[i];
      i = 1;
      yield permutation;
    } else {
      c[i] = 0;
      ++i;
    }
  }
}

function* permuteGroups(input) {
  input.sort((a,b) => {return a.length-b.length;});
  let groups = [], //Holds the list of Generators and words
      groupsCache = [], //Copy of groups to reset the Generators
      g = 0, i = input.length, len = input[i - 1].length,
      gid = 0, currentGroup, currentSet;

  //Helper function to reset a Generator
  function reset(gid) {
    groups[gid] = {
      'currentValue': undefined,
      'generator': permute(groupsCache[gid].split(','))
    };
  }
  function fetch(gid, next) {
    let group = groups[gid];

    // IF next and next === true
    if (!!next) {
      if (group.generator === undefined) return { 'currentValue': group.currentValue };

      let cv = group.generator.next();
      group.currentValue = (cv.done ? 'done' : (cv.value ? cv.value.join(',') : undefined));
    }

    return {
      'currentValue': group.currentValue
    };
  }
  function getOutput(next) {
    return groups.map((group, index) => fetch(index, next).currentValue);
  }

  //First move words into sub-arrays based on length
  groups.push([]);
  while (i--) {
    if (input[i].length == len) {
      groups[g].push(input[i]);
      continue;
    }
    groups[++g] = [input[i]];
    len = input[i].length;
  }
  groupsCache = groups.map(x => x.join(',')); // Convert each group into a string to preserve order
  //Turn the sub-arrays into Generators if they have more than one item
  groups = groups.map(group => (group.length > 1 ? { 'currentValue': undefined, 'generator': permute(group.toString().split(',')) } : { 'currentValue': group.toString().split(','), 'generator': undefined }) );
  //Yield initial output
  yield getOutput(true);

  let index = 0, isInc = false;
  while (true) {
    // If we're supposed to be going up to the next group, but there isn't one, reset the index back to zero
    // Fetch the next value for the current group...
    currentSet = fetch(index, true);
    // If this was the last value before this group is done...
    if (currentSet.currentValue == 'done' || Array.isArray(currentSet.currentValue)) {
      // reset the current group
      reset(index);
      // and put it back on the first value
      fetch(index, true);
      // Move on to the next group
      index++;
      if (index === groups.length) {
          // We're done!
          return;
      }
      // Mark that we plan on going to the next group up
      isInc = true;
      continue;
    }
    // and yield it.
    yield getOutput();
    // Otherwise if it is not the last value and the isInc flag is set
    if (isInc) {
      // Reset the index back to zero
      index = 0;
      isInc = false;
    }
  }
}
// "yourself","hero","entire","blank","peg","usage","tot","debate","volt","lie","almond","baseball","sell","youngster","use","atom","left","sit","even","input","only","freight"
let perm = permuteGroups(["yourself","hero","entire","blank","peg","usage","tot","debate","volt","lie","almond","baseball","sell","youngster","use","atom","left","sit","even","input","only","freight"]), i = 1;
let result = perm.next();
while (!result.done) {
  console.log(i++, result.value.toString());
  result = perm.next();
}
...