Wariacje bez powtórzeń

0

Cześć nie mam poomysłu jak wygenerować n elementowych wariacji bez powturzeń z zbioru x elementowego. Czy mógłby ktoś pomóc, długo już się z tym meczę i nie mam pomysłu?

0

A masz może link do poradnika jak to zrobic bez uzywanie zewnetrznych bibliotek na lekcjach mozemy tylko uzywac iostream?

1

Biblioteka standardowa nie jest zewnętrzną biblioteką.

0

Tak wiem, ale mi pozwalaja pisac tylko w czystym c bez stl.

0

No to stosuj zasadę opisaną w poście. Wymieszaj zbiór z wartościami, weź n pierwszych.

1

Przykładowy sposób wyliczania wszystkich wariacji. Jakkolwiek to nie jest rozwiązanie zadania.

#include <stdio.h>
#include <stdbool.h>

int
bit_add(
  int *t
, int t_n
){  int i;
    for( i = 0; i != t_n; i++ )
        if( !t[i] )
        {   t[i] = true;
            for( int j = 0; j != i; j++ )
                t[j] = false;
            break;
        }
    return i == t_n;
}

int
bit_count(
  int *t
, int t_n
){  int r = 0;
    for( int i = 0; i != t_n; i++ )
        if( t[i] )
            r++;
    return r;
}

int
silnia( int n
){  if( !n )
        return 1;
    return n * silnia( n - 1 );
}

int
main(
  int argc
, char *argv[]
){  int n = 10;
    int k = 2;
    int a[n];
    int b[n];

    for( int i = 0; i != n; i++ )
        a[i] = i;
    for( int i = 0; i != n - 1; i++ )
        printf( "%d, ", a[i] );
    printf( "%d\n", a[ n - 1 ] );

    for( int i = 0; i != k; i++ )
        b[i] = true;
    for( int i = k; i != n; i++ )
        b[i] = false;

    printf( "permutacji: %d\n", silnia(n) / silnia( n - k ));
    do
    {   if( bit_count( b, n ) == k )
        {   for( int i = 0; i != n - 1; i++ )
                printf( "%d, ", b[i] );
            printf( "%d\n", b[ n - 1 ] );
        }
    }while( !bit_add( b, n ));
}
1

STFW:

void GenArrangement(int n, int k, int idx, int used, int arran) {
    if (idx == k) {
        std::cout << arran << std::endl;
        return;
    }

    for (int i = 0; i < n; i++) 
        if (0 == (used & (1 << i))) 
            GenArrangement(n, k, idx + 1, used | (1 << i), arran * 10 + (i + 1));
}

int main()
{
    GenArrangement(3, 2, 0, 0, 0);
}

źródło: https://stackoverflow.com/questions/54970636/how-can-i-make-an-algorithm-in-c-for-finding-variations-of-a-set-without-repet
info: https://pl.wikipedia.org/wiki/Wariacja_bez_powt%C3%B3rze%C5%84
PS "bez powturzeń", domyślam sie, że chodziło o wariacje bez powtórzeń ;P

1 użytkowników online, w tym zalogowanych: 0, gości: 1