sorting an array by pattern -- javascript

Question

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']))

It's not clear what exactly the pattern is, can you give more examples? — CertainPerformance
– CertainPerformance, Commented Oct 24, 2018 at 4:04
the pattern would be ['one', 'two', 'three'], given an array of ['one', 'one', 'two', 'two', 'three', 'one'] the output should be ['one', 'two', 'three', 'one', 'two', 'one'] — totalnoob
– totalnoob, Commented Oct 24, 2018 at 4:06
I can solve this with a map. but I wanna figure out how to do it without one — totalnoob
– totalnoob, Commented Oct 24, 2018 at 4:11

slider · Accepted Answer · 2018-10-24 04:16:14Z

1

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);

answered Oct 24, 2018 at 4:16

slider

13.1k1 gold badge29 silver badges45 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

amrender singh · Accepted Answer · 2018-10-24 04:57:53Z

1

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);

edited Oct 24, 2018 at 4:57

answered Oct 24, 2018 at 4:19

amrender singh

8,2594 gold badges27 silver badges30 bronze badges

3 Comments

totalnoob Over a year ago

what does i = i % pattern.length; do?

amrender singh Over a year ago

@totalnoob it is mainly used to generate the index, and it ensures that the index never exceeds the array length.

HMR Over a year ago

You don't need to provide a pattern array when you use a Map, it'll work because you can get values in the order that you are putting them in (see my answer).

customcommander · Accepted Answer · 2018-12-12 11:54:05Z

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:

{ one: 3, two: 2, three: 1 } ~> ['one', 'two', 'three']
{ one: 2, two: 1, three: 0 } ~> ['one', 'two']
{ one: 1, two: 0, three: -1 } ~> ['one']
{ 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)

);

HMR · Accepted Answer · 2018-12-12 08:11:20Z

0

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())));

edited Dec 12, 2018 at 8:11

answered Dec 12, 2018 at 7:59

HMR

39.5k26 gold badges99 silver badges175 bronze badges

Collectives™ on Stack Overflow

sorting an array by pattern -- javascript

4 Answers 4

Comments

3 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

3 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related