Re: разбиение множества с
PROCEDURE Split (VAR c: SET; OUT s1: SET);
VAR x, n, n1: INTEGER;
BEGIN
x := MIN(SET); n := 0;
WHILE x <= MAX(SET) DO
IF x IN c THEN INC(n) END;
INC(x)
END; ASSERT(n MOD 3 = 0);
x := 0; n1 := 0; s1 := {};
WHILE n1 < n DIV 3 DO
IF x IN c THEN INCL(s1, x); EXCL(c, x); INC(n1) END;
INC(x)
END
END Split;
Какая-то странная функция:
1. во-первых в задаче требовалось разбить множество на все возможные варианты
т.е. на выходе должно быть много вариантов, а не один
2. не понятно, как адаптировать функцию, если множество состоит из строк или чисел с плавающей точкой
3. не понятно, сколько это функция будет работать для множества {int.MinValue;int.MaxValue}
1. во-первых в задаче требовалось разбить множество на все возможные варианты
т.е. на выходе должно быть много вариантов, а не один
2. не понятно, как адаптировать функцию, если множество состоит из строк или чисел с плавающей точкой
3. не понятно, сколько это функция будет работать для множества {int.MinValue;int.MaxValue}
понял
Заботай haskell, напиши прогу в 5-10 строк кода.
static void Swap(int[] items, int i, int j)
{
int tmp = items[i];
items[i] = items[j];
items[j] = tmp;
}
static void Swap(int[] items, int source, int target, int len)
{
for (int i = 0; i < len; ++i)
Swap(items, source + i, target + i);
}
static bool Next(int[] items, int n)
{
for (int i = n - 1; i >= 0; --i)
{
for (int j = n; j < items.Length - (n - i) + 1; ++j)
{
if (items[j] > items[i])
{
Swap(items, i, j, n - i);
Array.Sort(items, n, items.Length - n);
return true;
}
}
}
return false;
}
public static void Main
{
int[] items = new int[] { 3, 1, 5, 1, 4, 2 };
int k = items.Length / 3;
Array.Sort(items);
for (; ; )
{
foreach (int item in items)
Console.Write("{0} ", item);
Console.WriteLine;
if (!Next(items, k
break;
}
}
Если элементы множества:
не поддерживают сравнение,
или элементы массива имеют высокие накладные расходы при перемещениях,
или нет возможности менять входное множество,
то тогда перебираются индексы элементов, а не сами элементы.
не поддерживают сравнение,
или элементы массива имеют высокие накладные расходы при перемещениях,
или нет возможности менять входное множество,
то тогда перебираются индексы элементов, а не сами элементы.
А это не слишком долго? Я там вижу сортировку на каждом шаге... Простая рекурсия ИМХО будет быстрее...
#include <iostream>
#include <set>
#include <vector>
template< class A >
void process_rec( const std::vector< A >& vals, std::vector< bool >& tmp,
size_t cur, size_t count, std::vector< std::set< A > >& result )
{
if ( !count )
{
result.push_back( std::set< A >( ) );
std::set< A >& s = result[ result.size - 1 ];
for ( std::vector< bool >::const_iterator it = tmp.begin;
it != tmp.end; ++it )
{
if ( *it )
{
s.insert( vals[ it - tmp.begin ] );
}
}
return;
}
if ( cur >= vals.size )
{
return;
}
tmp[ cur ] = false;
process_rec( vals, tmp, cur + 1, count, result );
tmp[ cur ] = true;
process_rec( vals, tmp, cur + 1, count - 1, result );
tmp[ cur ] = false;
}
template< class A >
void process( const std::vector< A >& vals, std::vector< std::set< A > >& result )
{
size_t count3 = vals.size / 3;
std::vector< bool > tmp( vals.size false );
process_rec( vals, tmp, 0, count3, result );
}
int main
{
std::vector< int > vals;
vals.push_back( 1 );
vals.push_back( 5 );
vals.push_back( 8 );
vals.push_back( 12 );
vals.push_back( 14 );
vals.push_back( 156 );
std::vector< std::set< int > > result;
process( vals, result );
for ( std::vector< std::set< int > >::const_iterator it = result.begin;
it != result.end; ++it )
{
std::cout << "next\n";
for ( std::set< int >::const_iterator it1 = it->begin;
it1 != it->end; ++it1 )
{
std::cout << *it1 << " ";
}
std::cout << std::endl;
}
}
1. В теории можно без сортировки, т.к. там уже и так частично отсортированный результат получается, но думать лень.
2. Твои алгоритм на одиннаковых элементах лажается
3. Какое у тебя соотношение между кол-вом вызовов функции и кол-вом результатов?
2. Твои алгоритм на одиннаковых элементах лажается
vals.push_back( 1 );
vals.push_back( 1 );
vals.push_back( 1 );
vals.push_back( 1 );
vals.push_back( 1 );
vals.push_back( 1 );
3. Какое у тебя соотношение между кол-вом вызовов функции и кол-вом результатов?
1) Ну ну
2) Не придирайся к мелочам. Нужно всего лишь поменять контейнер:
2) Не придирайся к мелочам. Нужно всего лишь поменять контейнер:
#include <iostream>
#include <set>
#include <vector>
template< class A >
void process_rec( const std::set< A >& vals, std::vector< bool >& tmp,
size_t cur, size_t count, std::vector< std::set< A > >& result )
{
if ( !count )
{
result.push_back( std::set< A >( ) );
std::set< A >& s = result[ result.size - 1 ];
size_t counter = 0;
for ( typename std::set< A >::const_iterator it = vals.begin;
it != vals.end; ++it )
{
if ( tmp[ counter ] )
{
s.insert( *it );
}
counter++;
}
return;
}
if ( cur >= vals.size )
{
return;
}
tmp[ cur ] = false;
process_rec( vals, tmp, cur + 1, count, result );
tmp[ cur ] = true;
process_rec( vals, tmp, cur + 1, count - 1, result );
tmp[ cur ] = false;
}
template< class A >
void process( const std::set< A >& vals, std::vector< std::set< A > >& result )
{
size_t count3 = vals.size / 3;
std::vector< bool > tmp( vals.size false );
process_rec( vals, tmp, 0, count3, result );
}
int main
{
std::set< int > vals;
vals.insert( 1 );
vals.insert( 5 );
vals.insert( 8 );
vals.insert( 12 );
vals.insert( 14 );
vals.insert( 156 );
std::vector< std::set< int > > result;
process( vals, result );
for ( std::vector< std::set< int > >::const_iterator it = result.begin;
it != result.end; ++it )
{
std::cout << "next\n";
for ( std::set< int >::const_iterator it1 = it->begin;
it1 != it->end; ++it1 )
{
std::cout << *it1 << " ";
}
std::cout << std::endl;
}
}
3) Очевидно что от рекурсии можно избавиться. Глубина никогда не больше количества элементов в множестве.
И вообще, смешно говорить об вызовах функции когда у тебя сложность алгоритма n*log(nи даже больше, сейчас лениво оценивать средний случайдля одного элемента а у меня n.
сложность здесь уж точно не n
в идеале, должно быть Cnk
если не считать сортировку, то у меня Cnk
у рекурсии обычно 2^n - не хочу сейча считать
в идеале, должно быть Cnk
если не считать сортировку, то у меня Cnk
у рекурсии обычно 2^n - не хочу сейча считать
Cnk на один элемент? Или на все множество сразу? У меня O(n) на один элемент, стопудово.
PS: даже меньше, так как после того как мы дошли до самого низа, можно не подниматся наверх для получения следующего элемента.
PS: даже меньше, так как после того как мы дошли до самого низа, можно не подниматся наверх для получения следующего элемента.
> 2) Не придирайся к мелочам. Нужно всего лишь поменять контейнер:
Не помогло, на одиннаковые элементы какой-то бред выдает:
result:
Не помогло, на одиннаковые элементы какой-то бред выдает:
vals.insert( 1 );
vals.insert( 1 );
vals.insert( 1 );
vals.insert( 1 );
vals.insert( 2 );
vals.insert( 2 );
result:
next
Press any key to continue . . .
Все правильно. А что ты хотел? 2 / 3 == 0. Получили одно пустое множество 
Элементов, в примере, 6, а не 2.
ps
Нигде же не оговаривается, что элементы различные.
ps
Нигде же не оговаривается, что элементы различные.
> Cnk на один элемент? Или на все множество сразу?
на все множество
> У меня O(n) на один элемент, стопудово.
на один элемент чего?
так общая сложность какая?
на все множество
> У меня O(n) на один элемент, стопудово.
на один элемент чего?
так общая сложность какая?
Оставить комментарий
oolko
Есть множество состояшее из N элементов. N делиться на 3.Плз напишите функцию,
которая всеми возможными способами разбивает N элементов на 2/3 и 1/3.