"А нука, гуру!" второй эпизод

[dr_mousefly]

"А нука, гуру!" второй эпизод

Требуется разложить все натуральные числа от 3 до M (например, M = 45) на натуральные же слагаемые в количестве 2 и более из множества 1, 2, ..., N. (например, N = 9), таким образом, чтобы ни одно слагаемое не повторялось.
М равняется сумме всех наутральных чисел от 1 до N.

Ваша функция должна принимать как параметр число N и возвращать массив от 3 до M, каждый элемент которого содержит множество разложений на слагаемые для соответствующего числа, где каждое разложение есть множество чисел его составляющих.
число N не будет превышать, скажем, 20.

пример решения для N=9:

Тільки зареєстровані користувачі бачать весь контент у цьому розділі

сортировать разложения по количеству членов не нужно.

оцениваются:
скорость решения
простота и читаемость кода
производительность полученного решения.

решения принимаются в течение суток с момента публикации задания.
*курсивом выделены уточнения для задротов.

поехали.

 

[Тыемураз]

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

 

[ChuguevMan]

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

Интриги, скандалы, расследование. Ощущения невероятные, ждем говнокода, делаем дворянские ставки!
Вам с циклом или с рекурсией?

 

[dr_mousefly]

боюсь что вот от него мы никогда не дождемся.
разве что нечто на езыке ершова...

 

[HelloWorld]

public static Map<Integer, List<List<Integer>>> run(Integer n, Integer minSize) {
	Map<Integer, List<List<Integer>>> result = new HashMap<Integer, List<List<Integer>>>();
	
	for (int decRep = 0; decRep < Math.pow(2, n); decRep++) {
		if (Integer.bitCount(decRep) >= minSize) {
			String binaryString =  Integer.toBinaryString(decRep);
			while (binaryString.length() < n) {
				binaryString = '0' + binaryString;
			}
			
			Integer sum = 0;
			List<Integer> sequence = new ArrayList<Integer>();
			
			for (int pos = 0; pos < binaryString.length(); pos++) {
				if (binaryString.charAt(pos) == '1') {
					sum += pos + 1;
					sequence.add(pos + 1); 
				}
			}
			
			if (result.get(sum) == null) {
				List<List<Integer>> newList = new ArrayList<List<Integer>>();
				newList.add(sequence);
				result.put(sum, newList);
			}
			else {
				result.get(sum).add(sequence);
			}
		}
	}
	
	return result;
}

второй параметр - минимальное кол-во слагаемых (в текущей формулировке задачи это 2)

результат для n=4 (9 - то дофига для форума)

------------------------------------- 4
1 3 
------------------------------------- 8
1 3 4 
------------------------------------- 9
2 3 4 
------------------------------------- 6
2 4 
1 2 3 
------------------------------------- 3
1 2 
------------------------------------- 10
1 2 3 4 
------------------------------------- 7
3 4 
1 2 4 
------------------------------------- 5
2 3 
1 4

без сортировки, как просили

 

[dr_mousefly]

супер. наверно задача слишком простая..

 

[HelloWorld]

зря выложил, надо было до завтра подождать. уверен, тут бы накопилась масса более интересных решений

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

 

[dr_mousefly]

зря выложил, надо было до завтра подождать. уверен, тут бы накопилась масса более интересных решений

та ладно, заработал призовой балл.
у нас как: кто первый встал, того и тапки.

 

[Тыемураз]

Дон Хулио ,скажиnt,не стыдно ВАм показывать код ,не обеспеченный коментариями , а также пояснениями по использованию того или иного библиотечного метода ,в целом реализующих проект ?
Или как Вас понимать, оценивая Вашу работу ?
Вполне вероятным окажется тот факт,что комиссия сочтет неудовлетворительным применение какого сь метода по определеным соображениям ,имеющимися во внутренней среде оценщика ,которые вы в праве будете в дальнейшем опротестовать .
Разве не об этом вы писали недавно в первой ветке грандиозного вхождения в мир развитого умоздравия ?

 

[HelloWorld]

Дон Хулио ,скажиnt,не стыдно ВАм показывать код ,не обеспеченный коментариями , а также пояснениями по использованию того или иного библиотечного метода ,в целом реализующих проект ?
Или как Вас понимать, оценивая Вашу работу ?
Вполне вероятным окажется тот факт,что комиссия сочтет неудовлетворительным применение какого сь метода по определеным соображениям ,имеющимися во внутренней среде оценщика ,которые вы в праве будете в дальнейшем опротестовать .
Разве не об этом вы писали недавно в первой ветке грандиозного вхождения в мир развитого умоздравия ?

понимаю ваше негодование. всё, что я использовал из "библиотечных методов" - это возведение в степень, перевод числа из десятичной системы счисления в двоичную и подсчет количества единиц в двоичной записи. если в конкретном языке программирования это не будет реализовано на уровне "библиотечных методов", как в Java, ну что ж, нужно будет написать руками, но алгоритм от этого не изменится

 

[dr_mousefly]

понимаю ваше негодование. всё, что я использовал из "библиотечных методов" - это возведение в степень, перевод числа из десятичной системы счисления в двоичную и подсчет количества единиц в двоичной записи. если в конкретном языке программирования это не будет реализовано на уровне "библиотечных методов", как в Java, ну что ж, нужно будет написать руками, но алгоритм от этого не изменится

надо будет сделать прием решений личкой...

 

[strenzer]

надо будет сделать прием решений личкой...

тогда уже 2-3 ем членам экспертного совета!

Дон Хулио ,скажиnt,не стыдно ВАм показывать код ,не обеспеченный коментариями , а также пояснениями по использованию того или иного библиотечного метода ,в целом реализующих проект ?
Или как Вас понимать, оценивая Вашу работу ?
Вполне вероятным окажется тот факт,что комиссия сочтет неудовлетворительным применение какого сь метода по определеным соображениям ,имеющимися во внутренней среде оценщика ,которые вы в праве будете в дальнейшем опротестовать .
Разве не об этом вы писали недавно в первой ветке грандиозного вхождения в мир развитого умоздравия ?

Стыдно, когда видно.
Комиссии индефферентно. Даже мне.
Есть решение - это главное. По ответу уже видно, как автор делал, ну правда бдсм-ньюнсы типа двоичных строк не видны, но не в них соль.
А что скажет про онный код купечество?

 

[dr_mousefly]

однако, многие так активно соревновались в формальной логике,
а вот с решением задачи пока справился только один.
опять ТЗ не такое?

 

[strenzer]

Я "НЕ ВИЖУ СМЫСЛА". (с) Примерно концептуально, как решать понятно. Давайте задачу на женскую логику!

 

[dr_mousefly]

Я "НЕ ВИЖУ СМЫСЛА". (с) Примерно концептуально, как решать понятно. Давайте задачу на женскую логику!

Вас никто и не просит. Вам в прошлом раунде надавали по дисквалификации.

 

[strenzer]

А к кому же обращение? К преподам? К дворянам? Они смотрят горизонтально и такие задачи не решают .

 

[dr_mousefly]

А к кому же обращение? К преподам? К дворянам? Они смотрят горизонтально и такие задачи не решают .

вроде как в прошлом раунде были еще участники. так что ждем решений.

 

[strenzer]

например препод, не знающий русский язык?
https://www.kharkovforum.com/showpost.php?p=18610874&postcount=183
мы пропустили исступление. интересно, что на монголо-чукотском означает с..е?

 

[Achenar]

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

private static IEnumerable<List<int[]>> GetSequences( int n )
{
	var seq = new Sequence(n);
	var m = n*(n + 1)/2;
	var result = new List<int[]>[m - 2];
	while( seq.BitsUp > 0 )
	{
		if ( seq.BitsUp > 1 )
		{
			var ix = seq.Sum - 3;
			if (result[ix] == null) result[ix] = new List<int[]>();
			result[ix].Add(seq.Numbers);
		}
		seq.Raise(0);
	}
	return result;
}

class Sequence
{
	private readonly bool[] _data;
	public int BitsUp { get; private set; }
	public int Sum { get; private set; }

	public Sequence( int size )
	{
	        _data = new bool[size];
		_data[0] = true;
		_data[1] = true;
		BitsUp = 2;
		Sum = 3;
	}

	public int[] Numbers
	{
		get
		{
			var result = new List<int>();
			var weight = 1;
			foreach( var b in _data )
			{
				if (b) result.Add(weight);
				weight++;
			}
			return result.ToArray();
		}
	}
		
	public void Raise( int ix )
	{
		if (ix > _data.Length - 1)
		{
			BitsUp = 0;
			return;
		}
		_data[ix] = !_data[ix];
		var delta = _data[ix] ? 1 : -1;
		BitsUp += delta;
		Sum += delta * (ix + 1);
		if ( !_data[ix]) Raise( ix + 1);
	}
}

Результат для 5:

------------------------3
1 2

------------------------4
1 3

------------------------5
2 3
1 4

------------------------6
1 2 3
2 4
1 5

------------------------7
1 2 4
3 4
2 5

------------------------8
1 3 4
1 2 5
3 5

------------------------9
2 3 4
1 3 5
4 5

------------------------10
1 2 3 4
2 3 5
1 4 5

------------------------11
1 2 3 5
2 4 5

------------------------12
1 2 4 5
3 4 5

------------------------13
1 3 4 5

------------------------14
2 3 4 5

------------------------15
1 2 3 4 5

З.Ы. Решения HelloWorld не видел.

 

[dr_mousefly]

Achenar, нет времени пока посмотреть, но думаю мыслим в однм направлении.
а что это за стандарт кодирования, что фигурные скобки после if и foreach на другой строке?