Permutacje i sumowanie-trudności z użyciem next_permutation

Question

Niedawno prosiłem o pomoc w rozwiązaniu zadania

Niech X będzie zbiorem permutacji zbioru {1, 2, 3... n}. Niech f będzie funkcją liniową n zmiennych taką, że f(a_1, a_2, ... a_n)=1*a_1+2*a_2+... +n*a_n. Niech b_i to liczba permutacji x należących do X takich, że f(x)=i (mod n). Przykładowo dla n=3 mamy 6 permutacji x_1,x_2...x_6 = X mianowicie:

1,2,3=x_1

1,3,2=x_2

2,1,3=x_3

2,3,1=x_4

3,1,2=x_5

3,2,1=x_6

no i f(x_1)=14=2(mod 3), f(x_2)=13=1(mod 3)....f(x_6)=8=2(mod 3) i finalnie b_1=3, b_2=3, b_3=0.

Proszę o pomoc w napisaniu programu który mi napisze po kolei b_1...b_n

mam pewien pomysł jak to zrobić:

Najpierw(przed main) napisze sobie funkcje ktora mi sumuje domnożone elementy tablicy (funkcja f  tak jak wyżej) pozniej wchodze do programu wczytuje kolejne liczby od 1 do n w tablice i robie petle for ktora w jednym kroku stosuje funkcje f i komende next permutation i wyswietla wynik. niestety nie do konca wiem jak zrobic tą ostatnią pętlę for. Proszę o wskazówki, jak to zrobić lub wyjaśnienie co tak naprawde robi to next permutation, czy to w ogole dobry pomysl? początek programu mi się dobrze skompilował i działa.

#include <algorithm>
#include <string>
#include <iostream>
#include <stdio.h>
using namespace std;


int funkcja (int t[],int n)

{int wynik=0;
    for(int i=0;i<n;i++)
wynik=wynik+(i+1)*t[i];
return wynik;
}


main(){

    int k;
    cin >> k;
    int d[k];
    for(int i=0;i<k;i++)
        d[i]=i+1;

        // tu chciałbym zrobić pętlę ktora stosuje next permutation i pozniej wyznacza odpowiednią wartość za pomocą mojej funkcji
        //jak to zrobić...
      /*  sort(1,k);

        next_permutation(1,k);*/














}

 

Answer 1

std::sort(d, d + k);
do
{
  // Wypisz zawartość tablicy
  for (int i = 0; i < k; ++i)
  {
    std::cout << d[i] << ' ';
  }
  std::cout << '\n';
} while (std::next_permutation(d, d + k));

Tak się używa std::next_permutation ze zwykłą tablicą. Wklej sobie ten kodzik w miejsce komentarzy i kombinuj dalej ;)

---

Drobna uwaga: w linijce 21. tworzysz tablicę o zmiennym rozmiarze (jakbyś chciał coś więcej o tym poczytać, to googluj: variable length array). To rozwiązanie nie jest wspierane przez standard i akurat u Ciebie działa, ale na kompilatorze M$ (o ile mnie pamięć nie myli) już nie ruszy. Jeżeli chcesz mieć tablicę o zmiennym rozmiarze, to zainteresuj się wektorem (std::vector).

Comments

C++ nie ma VLA, C ma od C99 podajże.

---

@Piotr Batko, dzięki za odpowiedź! Jak wkleiłem Twój kod i włączyłem program  i wczytałem 8 to zaczął mi wypisywać 1 2 3 4 5 6 7 8 ciągle. coś źle wklejam?

#include <algorithm>
#include <string>
#include <iostream>
#include <stdio.h>
using namespace std;


int funkcja (int t[],int n)

{int wynik=0;
    for(int i=0;i<n;i++)
wynik=wynik+(i+1)*t[i];
return wynik;
}


main(){

    int k;
    cin >> k;
    int d[k];
    /*for(int i=0;i<k;i++)
        d[i]=i+1;*/
        std::sort(d, d + k);
do
{
  for(int i=0;i<k;i++)
        d[i]=i+1;
  for (int i = 0; i < k; ++i)
  {
    std::cout << d[i] << ' ';
  }
  std::cout << '\n';
} while (std::next_permutation(d, d + k));

}

 

---

liczyłem na to że wypisze mi wszystkie permutacje czy coś..

---

Linie 22 i 23 odkomentuj, a 27 i 28 usun.

Answer 2

Żebyś ruszył z miejsca...

#include <iostream>
#include <cstddef>
#include <algorithm>
#include <numeric>
#include <vector>

std::vector<std::size_t> generate_values(std::size_t n) {
    std::size_t counter = 1;
    std::vector<std::size_t> result;
    result.reserve(n);
    std::generate_n(std::back_inserter(result), n, [&] { return counter++; });
    return result;
}

std::size_t calculate_f(const std::vector<std::size_t>& values) {
    std::size_t counter = 1;
    std::size_t result = 0;
    for(const auto& val: values) {
        result += val * counter++;
    }
    return result;
}

void make_permutations(std::vector<std::size_t>& values) {
    do {
        for(const auto& val: values) {
            std::cout << val << ' ';
        }
        std::cout << "| f(a...) = " << calculate_f(values) << '\n';
    } while(std::next_permutation(values.begin(), values.end()));
}

int main() {
    std::size_t n;
    std::cin >> n;
    auto values = generate_values(n);
    make_permutations(values);
}