24 - lexicographic permutations

A permutation is an ordered arrangement of objects. For example, 3124 is one possible per-mutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alpha-betically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:

012   021   102   120   201   210

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

cevap : 2783915460

link

Derleme ortami Visual studio community c++

// project euler problem 24
// yasin tasan --> apr 2018
#include "stdafx.h"
#include <iostream>     // std::cout
#include <algorithm>    // std::next_permutation, std::sort
#include <string>

using namespace std;
void fact(unsigned int *n, unsigned int *fact);
void assign(unsigned int *j, unsigned int **matrix, unsigned int array[3], unsigned int *array_length);

int main() {
    unsigned int array[] = { 0,1,2,3,4,5,6,7,8,9};
    unsigned int array_length = (sizeof(array) / sizeof(*array));
    unsigned int total_permutation = 1;

    printf("list of digits = ");
    for (size_t i = 0; i < array_length; i++)
    {
        printf("%d ", array[i]);
    }
    printf("\n");

    fact(&array_length, &total_permutation); // factorial calculation for total permutation number 

    unsigned int **matrix = (unsigned int **)malloc(total_permutation * sizeof(unsigned int*)); // total_permutation aslinda matrix'in line sayisi

    for (size_t i = 0; i < total_permutation; i++)
    {
        matrix[i] = (unsigned int*)malloc(array_length * sizeof(unsigned int)); // array_length aslinda matrix'in column sayisi 
    }

    sort(array, array + array_length); // permutation list sorting

    unsigned int j = 0;
    do {
        assign(&j, matrix, array, &array_length);
        j++;
    } while (next_permutation(array, array + array_length));

    unsigned int counter = 0; // for line break

    for (size_t i = 0; i < total_permutation; i++)
    {
        counter = 0;
        printf("%d. permutation = ", i);
        for (size_t j = 0; j < array_length; j++)
        {
            printf("%d", matrix[i][j]);
            counter++;
            if (counter % array_length == 0)
            {
                printf("\n");
                if (i == 999999) // print 1000000. permutation
                {
                    i=total_permutation; // break
                }
            }
        }
    }

    return 0;
}

// factorial calculation for total permutation number 
void fact(unsigned int *n, unsigned int *fact)
{
    for (unsigned int i = 1; i <= *n; ++i)
    {
        *fact *= i; // factorial = factorial*i;
    }
}

// array assign to matrix (matrix)
void assign(unsigned int *j, unsigned int **matrix, unsigned int array[3], unsigned int *array_length)
{
    for (size_t i = 0; i < *array_length; i++)
    {
        matrix[*j][i] = array[i];
    }
}