Имам едномерен масив с елементи от A0 до А20 примерно. Искам да постигна пълно разбъркване на масива, по-точно искам да постигна всички възможни подреждания на масива, т. е. пермутация. След всяко подреждане съответно оперирам с елементите по определен начин в програмата. Трябва ми алгоритъм за постепенното разбъркване и изреждане на всички възможни подреждания.

Е затва програмиране се учи барабар с математиката.
Ти имаш ли си идея, че броят на 'всички възможни подреждания' на масив с 21 елемента е число, което е малко по-голямо от 51 и 18 нули зад него? Не знам как се казва, ама гарантирано е ужасно голямо и програмата ти няма да свърши до голямата имплозия, или каквото там е обратното на големия взрив.

System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

Редакция: Е поизхвърлих се бая. Ще свърши значително по-бързо. Ако генерираш по 1 млрд 'подреждания' на секунда, ще ти трябват от порядъка на 1 млрд секунди, което си е грубо казано няма и 150 години.

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

Редакция 2: Ааааа, ма наистина не мога да смятам. Малко над 1616 години са. Но все пак това си е направо скоро спрямо времето към което те изстрелях.

Редактирано от Colombino на 08.05.09 01:05.

Човека е решил, че за да се разбъркат добре, трябва да минат през всички пермутации. С какво право оспорваш такива основоположни хипотези?!

0xCodeFace

Интересно, а добър алгоритъм все пак знаеш ли?

Ми не знам, но едва ли ще е трудно да се намери ако знаеш какво да търсиш.
На прима виста ми идва следният рекурсивен алгоритъм (но не се сещам как ще се имплементира, трябва да се види става ли):

Ако имаш всички пермутации за масив с големина n, за да получиш всички за масив с големина n + 1, за всяка налична пермутация получаваш n+1 нови, като поставиш новия елемент на позиция от 0 до n+1.

System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_

малко нестандартно, в името на няколкото стотин спестени такта.

int crime_order( type elements[20], unsigned long long perm ) {

	for( int i = 20; i > 1; perm /= i-- ) swap<type>( elements + perm % i, elements + i - 1 );

	

	return perm ? 0: -1;

}

#include "stdio.h"

#include "string.h"

#include "time.h"



#define SIZE 21

#define EMPTY SIZE

unsigned char perm[SIZE];



void fperm(unsigned char Number)

{

    unsigned char i, j, count;



    if (SIZE == Number)

    {

        char buff[1 /*\n*/ + 1/*{*/ + 4*SIZE - 2 + 1/*}*/ + 1/*0*/];

        buff[0] = '\n';

        buff[1] = '{';



        for (i = 0; i < SIZE; i ++)

        {

            if (i != SIZE -1)

            {

                sprintf(buff + 2 + i * 4, "%2d, ", perm[ i]);

            }

            else

            {

                sprintf(buff + 2 + i * 4, "%2d", perm[ i]);

            }

        }

        buff[1 + 1 + 4*SIZE - 2] = '}';

        buff[1 + 1 + 4*SIZE - 2 + 1] = 0;

        printf(buff);

    }

    else

    {

        for (i = 0; i < SIZE - Number; i ++)

        {

            count = 0;

            for (j = 0; j < SIZE; j++)

            {

                if (EMPTY == perm[j])

                {

                    if (count >= i)

                    {

                        perm[j] = Number;

                        fperm(Number + 1);

                        perm[j] = EMPTY;

                        break;

                    }

                    count ++;

                }

            }

        }

    }

}



int main(int argc, char* argv[])

{

    time_t start, end;



    memset(perm, EMPTY, SIZE);



    time(&start);

    

    fperm(0);



    time(&end);



    printf("\n\nExecution time in second: %ld", end - start);



    getchar();



    return 0;

}

Редактирано от Tweeg на 08.05.09 22:18.

Хич не ти вървят сметките по нощите.

Айде 3-ти последен опит колко години са 1 милиард секунди :)

51 милярда, бе! Нали казах, че е 51 с 18 нули. Разделяме нулите на два множителя по 1 млрд грубо казано. Единият милиард го ползваме за да кажем, че ще ги правим по толкова в секунда.
Накрая пишем на Гугъл тва:
51 billion seconds in years
и готово. Иначе знам, че казах 1 млрд, па направих сметката за 51, ма ме домързя и тва да го фиксвам.

System Doctor Error:
Your girlfriend is pregnant.
(A)bort, (M)arry, (I)gnore?_