Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Flash > ActionScript 3.0

Версия для печати  Отправить по электронной почте    « Предыдущая тема | Следующая тема »  
Опции темы Опции просмотра
 
Создать новую тему Ответ
Старый 25.11.2013, 14:34
feelgood66 вне форума Посмотреть профиль Отправить личное сообщение для feelgood66 Найти все сообщения от feelgood66
  № 1  
Ответить с цитированием
feelgood66
[+1 15.11.10]

Регистрация: Jun 2005
Сообщений: 25
По умолчанию Array. Перемешивание массива

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

Задача
приходит массив [x,x,x,y,y,y,y,y,y,z,z]

нужно его перемешать так, чтобы ни один элемент не стоял рядом с таким же
то есть
x,y,z,y,x,y... - допустимо
x,y,y... - не допустимо

Вроде тривиальная задача.. но вот закавыка..

Всем спасибо!

Старый 25.11.2013, 15:10
samana вне форума Посмотреть профиль Отправить личное сообщение для samana Найти все сообщения от samana
  № 2  
Ответить с цитированием
samana
 
Аватар для samana

блогер
Регистрация: Mar 2008
Адрес: Днепропетровск
Сообщений: 1,783
Записей в блоге: 3
Тогда ещё надо убедиться, что такой массив возможно создать. Допустим массив [x,x,y,y,y,y,y,y,y,y,z] невозможно так перемешать, так как "y" намного больше.

Старый 25.11.2013, 15:21
feelgood66 вне форума Посмотреть профиль Отправить личное сообщение для feelgood66 Найти все сообщения от feelgood66
  № 3  
Ответить с цитированием
feelgood66
[+1 15.11.10]

Регистрация: Jun 2005
Сообщений: 25
Цитата:
Сообщение от samana Посмотреть сообщение
Тогда ещё надо убедиться, что такой массив возможно создать. Допустим массив [x,x,y,y,y,y,y,y,y,y,z] невозможно так перемешать, так как "y" намного больше.
согласен абсолютно!
интересно, утверждение:
"сумма повторений любого элемента меньше половины длинны массива"
может считаться признаком того, что задача может быть выполнена?

что касается самой задачи. что-то мне подсказывает, что нужно несколько модифицировать метод пузырька

Старый 25.11.2013, 15:27
samana вне форума Посмотреть профиль Отправить личное сообщение для samana Найти все сообщения от samana
  № 4  
Ответить с цитированием
samana
 
Аватар для samana

блогер
Регистрация: Mar 2008
Адрес: Днепропетровск
Сообщений: 1,783
Записей в блоге: 3
По идее, сумма одинаковых элементов может быть "половина массива +1", что бы такой массив можно было правильно размешать.

Старый 25.11.2013, 15:33
feelgood66 вне форума Посмотреть профиль Отправить личное сообщение для feelgood66 Найти все сообщения от feelgood66
  № 5  
Ответить с цитированием
feelgood66
[+1 15.11.10]

Регистрация: Jun 2005
Сообщений: 25
ну.. я бы даже сказал точнее - в зависимости от длины массива
если длина четная - то не более ровно половины
если нет - то допустимо половина + 1
вроде так
если смотреть "на пальцах"
то
[x,x,x,y,y,y] -> [x,y,x,y,x,y]
а вот
[x,x,x,x,y,y,] -> уже никак

зато
[x,x,x,x,y,y,y] -> [x,y,x,y,x,y,x]

Старый 25.11.2013, 15:37
Hauts вне форума Посмотреть профиль Отправить личное сообщение для Hauts Посетить домашнюю страницу Hauts Найти все сообщения от Hauts
  № 6  
Ответить с цитированием
Hauts
 
Аватар для Hauts

блогер
Регистрация: Feb 2008
Адрес: Россия, Новосибирск, Академгородок
Сообщений: 2,112
Записей в блоге: 1
Отправить сообщение для Hauts с помощью ICQ Отправить сообщение для Hauts с помощью Skype™
Попробуйте так:

Код AS3:
var a:Array = [0,2,0,0,0,1,1,1,0,2,0,2,0,2,0,1,0,1,1,2,1,2,1,2,0,1,2,1,0,1];
 
 
function smartSort(array:Array):Array {
	var array:Array = array.concat().sort();
	var elements:Array = [];
	var elementsLengths:Array = [];
	var totalRendomElements:int = 0;
	var k:int;
	for (k = 0; k < a.length; k ++) {
		var el:* = array[k];
		var index:int = elements.indexOf(el);
		if (index == -1) {
			totalRendomElements++;
			elements.push(el);
			index = elements.length - 1;
			elementsLengths[index] = 0;
		}
		elementsLengths[index]++;
	}
	var maxGroupLength:int = elementsLengths.concat().sort()[0];
	var newArray:Array = [];
	for (k = 0; k < maxGroupLength; k ++) {
		for (var j:int = 0; j < totalRendomElements; j ++) {
			elementsLengths[j]--;
			if (elementsLengths[j] >= 0) {
				newArray.push(elements[j]);
			}
		}
	}
	return newArray;
}
 
trace(a)
trace(smartSort(a))
Особо не тестировал.
__________________
hauts.ru

Старый 25.11.2013, 15:37
samana вне форума Посмотреть профиль Отправить личное сообщение для samana Найти все сообщения от samana
  № 7  
Ответить с цитированием
samana
 
Аватар для samana

блогер
Регистрация: Mar 2008
Адрес: Днепропетровск
Сообщений: 1,783
Записей в блоге: 3
Цитата:
ну.. я бы даже сказал точнее - в зависимости от длины массива
если длина четная - то не более ровно половины
если нет - то допустимо половина + 1
Да, да, правильно. Всё надо проверять.

Старый 25.11.2013, 15:46
feelgood66 вне форума Посмотреть профиль Отправить личное сообщение для feelgood66 Найти все сообщения от feelgood66
  № 8  
Ответить с цитированием
feelgood66
[+1 15.11.10]

Регистрация: Jun 2005
Сообщений: 25
Цитата:
Сообщение от Hauts Посмотреть сообщение
Попробуйте так:

Особо не тестировал.
и что характерно - работает!
Гениально! Hauts, браво!
премного благодарен!

Старый 25.11.2013, 16:01
Hauts вне форума Посмотреть профиль Отправить личное сообщение для Hauts Посетить домашнюю страницу Hauts Найти все сообщения от Hauts
  № 9  
Ответить с цитированием
Hauts
 
Аватар для Hauts

блогер
Регистрация: Feb 2008
Адрес: Россия, Новосибирск, Академгородок
Сообщений: 2,112
Записей в блоге: 1
Отправить сообщение для Hauts с помощью ICQ Отправить сообщение для Hauts с помощью Skype™
You are welcome.
__________________
hauts.ru

Создать новую тему Ответ Часовой пояс GMT +4, время: 15:52.
Быстрый переход
  « Предыдущая тема | Следующая тема »  

Теги
array , sort
Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


 


Часовой пояс GMT +4, время: 15:52.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.