sorting an array by pattern -- javascript

user_2548965 0
Viewed 480

for an array of 

['one', 'one', 'two', 'two',  'three', 'one']

use the pattern ['one', 'two', 'three'] to turn that into

['one', 'two', 'three', 'one', 'two', 'one']

my thought is

const sortArray = oldArray => {
let newArr = [];

while (newArr < oldArray.length) {
    // loop through array
    for (let i = 0; i < arr.length; i++) {
        // loop through pattern
        for (let j = 0; j < pattern.length; j++) {
            // match
            if (arr[i] === pattern[j]) {
                // add item to new array
                newArr.push(arr[i]);
                // remove item from old array
                arr.shift();
            } else {
                // push item to end of array
                arr.push(arr[i]);
                // remove item from array
                arr.shift()
            }
        }
    }
}

    return newArray;
}

I can do this using a map, it's what I'm used to for solving stuff like this but when it comes to iterating through just an array with a pattern I get super confused. any suggestions?

with a map, this is how I'd do it

let a = ['one', 'one', 'two', 'two',  'three', 'one'];

const printValues = (arr, pattern) => {
  let map = {};
  let a = [];

  arr.forEach((v) => {
    if (!map[v]) map[v] = 1;
    else map[v]++;
  })

  while (a.length !== arr.length) {
    pattern.forEach((v) => {
      if (map[v] > 0) {
        a.push(v);
        map[v]--;
      }
    })
  }

  console.log(a);
}

console.log(printValues(a, ['one', 'two', 'three']))

javascript
4 Answers

I think you have the right idea, but you want to iterate through the pattern array first to preserve the ordering, and then go about looking in oldArray. In the following solution, I'm also using a set to store indices that have already been used.

const oldArray = ['one', 'one', 'two', 'two', 'three', 'one'];
const pattern = ['one', 'two', 'three'];

let newArray = [];
let added = new Set();

while (newArray.length < oldArray.length) {
  for (let p of pattern) {
    for (let i = 0; i < oldArray.length; i++) {
      if (!added.has(i) && oldArray[i] === p) {
        added.add(i);
        newArray.push(p);
        break;
      }
    }
  }
}
console.log(newArray);

user_18226980

Try the following :

  • count frequency of all the elements in your pattern.
  • Than simply iterate over the pattern array and keeping pushing each element one by one(until every element count is zero).

let arr = ['one', 'one', 'two', 'two',  'three', 'one','three'];
let freq = arr.reduce((a,curr)=>{
  a[curr] = (a[curr] || 0)+1;
  return a;
},{});
let len =  Object.keys(freq).length;
let result = [];
let pattern = ["one", "two", "three"];
let i = 0;

while(len){
  if(freq[pattern[i]]){
    result.push(pattern[i]);
    freq[pattern[i]] --;
  } else
    len--;
  i++;
  i = i % pattern.length;
}
console.log(result);

user_65142310

This is an interesting problem!

Notice: you don't really tell what to do with elements unknown to the pattern. Should they all come at the beginning or the end or spread evenly? I've decided to ignore that.

If you see your pattern as a seed to produce a new array rather than as an iteration constraint on an existing one, the problem is easier to solve IMHO.

You can create a function that accepts a pattern along with the frequencies of each element:

createFromPattern({one: 3, two: 2, three:1}, ['one', 'two', 'three']);

Generating the frequencies is easy:

const count = list => list.reduce((acc, cur) => ({...acc, [cur]: (acc[cur] || 0) + 1}), {});

count(['one', 'one', 'two', 'two',  'three', 'one']);
//=> { one: 3, two: 2, three: 1 }

Let's visualise how the function would work:

  1. { one: 3, two: 2, three: 1 } ~> ['one', 'two', 'three']
  2. { one: 2, two: 1, three: 0 } ~> ['one', 'two']
  3. { one: 1, two: 0, three: -1 } ~> ['one']
  4. { one: 0, two: -1, three: -2 } ~> [] STOP

If you aggregate each intermediary result, you end up with your final array. This can be done recursively:

const createFromPattern = (opts, seed) => {
  const newOpts = {...opts};
  const pick = seed.reduce((acc, cur) => [...acc, ...(newOpts[cur] ? newOpts[cur]-- && [cur] : [])], []);
  const stop = Math.max(...Object.values(newOpts)) <= 0;
  return [].concat(pick, (!stop ? createFromPattern(newOpts, seed) : []));
};

Putting this altogether:

const list = ['one', 'one', 'two', 'two',  'three', 'one']
const pattern = ['one', 'two', 'three']

const count = list => list.reduce((acc, cur) => ({...acc, [cur]: (acc[cur] || 0) + 1}), {});

const createFromPattern = (opts, seed) => {
  const newOpts = {...opts};
  const pick = seed.reduce((acc, cur) => [...acc, ...(newOpts[cur] ? newOpts[cur]-- && [cur] : [])], []);
  const stop = Math.max(...Object.values(newOpts)) <= 0;
  return [].concat(pick, (!stop ? createFromPattern(newOpts, seed) : []));
};

console.log(

  createFromPattern(count(list), pattern)

);

user_12448840

The other answers come close but you don't need a pattern array if you use Map. The order you add keys will be the order you can get them out.

You should use Map instead:

const arr = ['one', 'one', 'two', 'two', 'three', 'one'];
const map = arr.reduce(
  (result, item) =>
    result.set(item, (result.get(item) || []).concat(item)),
  new Map(),
);
const transform = (arr) => {
  const recur = (arr, result, index, max) => {
    if (index === max) {
      return result;
    }
    return recur(
      arr,
      result.concat(arr.map((item) => item[index])),
      index + 1,
      max,
    );
  };
  return recur(
    arr,
    [],
    0,
    Math.max(...arr.map((item) => item.length)),
  ).filter((x) => x !== undefined);
};
console.log(transform(Array.from(map.values())));

user_16419410
Related