Алгоритм превращения одноуровневого списка в двухуровневый?

Question

[dom1n1k]

Есть массив, содержащий элементы двух типов (хотя в общем случае типов может быть и больше двух, но пока что можно на это забить). Конкретные объекты неважны, пусть для наглядности это будут числа и буквы. Нужно объединить идущие подряд однотипные элементы в подмассивы. Например:

[1, 2, a, b] => [[1, 2], [a, b]]
[1, 2, 3, a, 4, 5, b, 9, n, m] => [[1, 2, 3], [a], [4, 5], [b], [9], [n, m]]
[1] => [[1]]
[a] => [[a]]
[] => []

Вроде бы совсем не сложная задача, но решения получаются что-то ну очень корявые. Наверняка есть какое-то красивое и изящное, но видимо я туплю.

Answer 1

[Rsa97]

var arr = [1, 2, 3, 'a', 4, 5, 'b', 9, 'n', 'm'];
arr = arr.reduceRight(function(prev, el, i) {
  if (prev.length == 0 || 
     (typeof(el) != typeof(prev[0][0]))) {
    prev.unshift([el]);
  } else {
    prev[0].unshift(el);
  }
  return prev;
}, []);
console.log(JSON.stringify(arr));

[[1,2,3],["a"],[4,5],["b"],[9],["n","m"]]

Comments

[dom1n1k]

Я и сам думал о методах reduce, но они мне кажутся не очень наглядными.
Собственно, я и сейчас смутно понимаю, как ваш код работает :)

[Rsa97]

dom1n1k: reduce работает очень просто. в начале задаётся аккумулятор, затем для каждого элемента массива вызывается функция, в которую передаётся текущее значение аккумулятора, значение текущего элемента массива и его позиция. Функция возвращает новое значение аккумулятора.
reduceRight обходит массив в обратном порядке, здесь это удобнее, чтобы постоянно работать с нулевым элементом аккумулятора.

[Rsa97]

dom1n1k: Собственно, то же самое можно сделать и на обычном цикле.

var arr = [1, 2, 3, 'a', 4, 5, 'b', 9, 'n', 'm'];
var res = [];
for (let i = arr.length-1; i >= 0; i--) {
  if (res.length == 0 || 
     (typeof(arr[i]) != typeof(res[0][0]))) {
    res.unshift([arr[i]]);
  } else {
    res[0].unshift(arr[i]);
  }
}
console.log(JSON.stringify(res));

Answer 2

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

Надо двигаться по значениям, по одному, запоминая текущий «класс» значения. При смене создавать новый подмассив, в который пихать очередное значение.

Рабочий пример:

// классификатор – возвращает название класса
// к которому относится переданное значение
// неважно, как называть классы, лишь бы по-разному
function classify(i) {
	if(  typeof i === "number") return "my_number";
	return "my_string";  
}

// группирует в подмассивы идущие подряд
// значения одного класса
function group(a) {
  var i, item, c={prev:null, curr:null}, result=[], to;
  
  for(i=0; i<a.length; i++) {
    item = a[i];
    c.curr = classify(item);
    if(!c.prev || c.prev !== c.curr) {
      c.prev = c.curr;
      result.push([]);
      to = result[result.length-1];
    }
    to.push(item);
  }
  return result;
}

Answer 3

[dmz9]

посидел на кодеварс - полюбил "сразу-возврат".
и кстати задачка кажется с какого то подобного ресурса.
ну вобщем, аккумулятором может быть необязательно массив, это может быть и объект, в котором хранятся флаги, вместо заведения переменных через var или запиливания еще одних функций.
алсо - зачем запускать "тяжелый" алгоритм если у нас на входе пусто/одно-элементный массив? сразу возвращаем [array].
единственный минус решения - два раза вызывается typeof в случаях когда он не совпадает.
ещё один чит-код - reduce вернет аккумулятор. а аккумулятор это объект. а к свойству объекта (result) можно обратиться через точку.
не будем слепо добавлять в массивы, для этого есть текущий ключ итератора acc.i (который увеличивается когда появился другой тип элемента).
ну и изначально он = -1, потому что первое же несоответствие last:false !== "какой-то-там-тип-значения" его плюсанет и он станет ноликом.
и еще - мне это нравится потому что тут всего одна проверка, всё остальное достаточно прямолинейно.
нет необходимости делать проверки существования начальных значений "флагов" - главное правильно их задать сразу

function groupByType(array) {
    return (array.length < 2) ? [array] : array.reduce(function(acc, current) {
    	if(typeof current != acc.last){
    		acc.last=typeof current;
    		acc.result.push([]);
    		acc.i++;
    	}
    	acc.result[acc.i].push(current);
        return acc;
    }, { result: [], i: -1,last:false }).result;
};

опдейт.:
подумав и окинув взглядом - можно избавиться и от итератора, он не нужен.

function groupByType(array) {
    return (array.length < 2) ? [array] : array.reduce(function(acc, current) {
    	if(typeof current != acc.last){
    		acc.last=typeof current;
    		acc.result.push([]);
    	}
    	acc.result[acc.result.length-1].push(current);
        return acc;
    }, { result: [] ,last:false }).result;
};
groupByType([1, 2, 3, 'a', 4, 5, 'b', 9, 'n', 'm']);

Comments

[dom1n1k]

Нет, задача абсолютно практическая, из реального проекта (хоть и с приставкой pet, но всё же).
Хотя вполне возможно, что где-то и встречалась.

Answer 4

[dom1n1k]

Вот что я сам родил и что можно назвать более-менее приличным:

function group (input) {

	var last = function (arr) {
		return arr[arr.length - 1];
	}

	var output = [];
	input.forEach(function (el) {
		if (output.length === 0 || typeof(el) !== typeof(last(output)[0])) {
			output.push([]);
		}
		last(output).push(el);
	});

	return output;
}

Answer 5

[Dark Hole]

ES6 может быть элегантнее?

let arr = [...], result = [[]], cur = 0;
for(let val of arr)
  if(arr[cur].length == 0 || typeof arr[cur][0] == typeof val) arr[cur].shift(val);
  else cur++, arr[cur] = [val];