Bonjour à tous,

Ça n'a pas grand'chose à voir avec le C, mais comme il n'y a pas de forum algorithme, je poste ici.

Comment remplir une matrice carrée de taille N (>3), avec les nombres de 1 à N dans chaque ligne, mais en s'arrangeant pour qu'il n'y ait qu'une occurence de chaque nombre par colonne ?

Exemple:

Ok

! Ok

D'avance un grand merci.

Edgar;

-
Edité par edgarjacobs 21 février 2022 à 16:15:40

Bonjour,

tu crées une matrice qui possède cette propriété comme :

0 1 2 3
1 2 3 0
2 3 0 1
3 0 1 2

puis tu utilises un fisher yates pour mélanger les colonnes et/ou les lignes.

Du moins c'est ma première idée comme ça de but en blanc.

Merci à toi, j'y avais déjà pensé, maisil est probable que je me retrouve avec deux nombres identiques dans une colonne (c'est là tout le problème).

Pourquoi ?

Échanger deux colonnes ne pose aucun problème pour les colonnes (il y a aura toujours une occurrence de chaque chaque chiffre dans ces colonnes) et on échange deux nombres forcément différents dans une ligne. Idem pour l'échange de ligne, mais transposé.

Donc si tu mélanges les colonnes et si ce n'est pas suffisant les lignes tu devrais garder la propriété «une occurrence par ligne et colonne».

Bonjour,

Tu n'indiques pas si si tu as d'autres contraintes. Sinon il suffit de remplir la matrice avec forme de l'exemple de WhiteCrow:
première ligne: 1, 2, ..., N-1, N
seconde ligne : 2, 3, ..., N, 1
troisième ligne: 3, ..., N, 1, 2
...
dernière ligne : N, 1, ...N-2, N-1.

Par construction, on n'a jamais 2 même nombres sur chaque ligne et chaque colonne et en plus on obtient une matrice symétrique.

ce qui donne m[r][c] =  1 + (r+c) % N; pour tous r et c entre 0 et N-1

-
Edité par michelbillaud 21 février 2022 à 16:29:09

C'était clair pour moi, mais évidemment pas pour vous. Désolé. Ce que je souhaite faire, c'est un skyscrapers, mais avec une présentation différente, en "3d" et en couleur.

-
Edité par edgarjacobs 21 février 2022 à 16:33:30

Bah tu as toute une floppée de transformations qui laisse ta contrainte valide comme l'échange de colonne, l'échange de lignes (ce qui permet de faire un fisher yates), l'ajout d'une constante à chaque cellule (modulo ton range), l'échange de toutes les occurrences d'une valeur avec celles d'une autre, rotations, translations, symétrie horizontale/verticale …

Sinon tu as la possibilité d'essayer de dénombrer toutes les grilles possibles, de trouver une fonction qui à un entier associe une matrice possédant la propriété skyscrapers et d'en choisir une uniformément dans cet intervalle d'entiers (mais c'est un peu overkill en sachant qu'un fisher yates est amplement suffisant).

La difficulté est de montrer que pour toute paire de matrices qui ont la propriété indiquée, il existe toujours une séquence de permutations qui permet de passer de l'une à l'autre.

White Crow a écrit:

(...) Sinon tu as la possibilité d'essayer de dénombrer toutes les grilles possibles (....)

C'était mon idée de départ: générer toutes les grilles possibles, mettre le tout dans un fichier, et faire un rand() sur le nombre de lignes du fichier pour sélectionner un problème à résoudre.

Et de 9 x 9 avec la contrainte supplémentaire qu'il y ai qu'une seule occurrence dans chaque groupe de 3x3 côte à côte (3x3 groupe de 3) ?

edgarjacobs a écrit:

White Crow a écrit:

(...) Sinon tu as la possibilité d'essayer de dénombrer toutes les grilles possibles (....)

C'était mon idée de départ: générer toutes les grilles possibles, mettre le tout dans un fichier, et faire un rand() sur le nombre de lignes du fichier pour sélectionner un problème à résoudre.

En fait ce sont les carrés latins, à propos desquels il y a toute une littérature.
https://math.stackexchange.com/questions/63131/generate-random-latin-squares

Les mettre dans un fichier, dans un gros alors. Si on les compte selon la taille N :

# A002860 (b-file synthesized from sequence entry)
1 1
2 2
3 12
4 576
5 161280
6 812851200
7 61479419904000
8 108776032459082956800
9 5524751496156892842531225600
10 9982437658213039871725064756920320000
11 776966836171770144107444346734230682311065600000

Sources

https://oeis.org/A002860

https://oeis.org/A002860/b002860.txt

Ci dessous un programme bourrin en Java

package remplissage;

import java.util.Arrays;

public class Remplissage {

    @FunctionalInterface
    interface Action {
        void execute(int[][] m);
    }

    public static void main(String[] args) {
        test(5);
    }

    private static void test(int n) {
        int[][] m = new int[n][n];
        var affiche = new Action() {
            int num = 0;

            @Override
            public void execute(int[][] mat) {
                num += 1;
                System.out.format("%d ", num);
                for (var row : mat) {
                    System.out.print(Arrays.toString(row));
                }
                System.out.println("");
            }
        };
        foreachGrid(m,  n, 0, 0, affiche);
    }

    private static void foreachGrid(int[][] m, int n, int r, int c, Action a) {
        // System.out.format("%d %d\n", r, c);
        if (r == n) {
            a.execute(m);
            return;
        }
        try_values:
        for (int candidate = 1; candidate <= n; candidate++) {
            for (int cc = 0; cc < c; cc++) {
                if (m[r][cc] == candidate) {
                    continue try_values;
                }
            }
            m[r][c] = candidate;
            for (int rr = 0; rr < r; rr++) {
                if (m[rr][c] == candidate) {
                    continue try_values;
                }
            }

            if (c + 1 == n) {
                foreachGrid(m, n, r + 1, 0, a);
            } else {
                foreachGrid(m, n, r, c + 1, a);
            }

        }
    }
}

qui affiche les 161280 résultats d'ordre 5

1 [1, 2, 3, 4, 5][2, 1, 4, 5, 3][3, 4, 5, 1, 2][4, 5, 2, 3, 1][5, 3, 1, 2, 4]
2 [1, 2, 3, 4, 5][2, 1, 4, 5, 3][3, 4, 5, 1, 2][5, 3, 1, 2, 4][4, 5, 2, 3, 1]
3 [1, 2, 3, 4, 5][2, 1, 4, 5, 3][3, 4, 5, 2, 1][4, 5, 1, 3, 2][5, 3, 2, 1, 4]
4 [1, 2, 3, 4, 5][2, 1, 4, 5, 3][3, 4, 5, 2, 1][5, 3, 2, 1, 4][4, 5, 1, 3, 2]
5 [1, 2, 3, 4, 5][2, 1, 4, 5, 3][3, 5, 1, 2, 4][4, 3, 5, 1, 2][5, 4, 2, 3, 1]
...
161278 [5, 4, 3, 2, 1][4, 5, 2, 1, 3][3, 2, 1, 4, 5][2, 1, 5, 3, 4][1, 3, 4, 5, 2]
161279 [5, 4, 3, 2, 1][4, 5, 2, 1, 3][3, 2, 1, 5, 4][1, 3, 5, 4, 2][2, 1, 4, 3, 5]
161280 [5, 4, 3, 2, 1][4, 5, 2, 1, 3][3, 2, 1, 5, 4][2, 1, 4, 3, 5][1, 3, 5, 4, 2]

En fait les 1344 dont la première ligne est [1,2,3,4,5],  en appliquant les 5! = 120 permutations.

-
Edité par michelbillaud 21 février 2022 à 18:11:03

L'avantage avec le listing c'est que ça reste de nos jours raisonnables point de vue taille et que tu peux proposer des grilles non déjà proposées. Du moins si tu ne veux pas proposer des grilles plus grande qu'un 5×5.

Sinon, ce que je proposais de chercher était une fonction (plus au sens mathématique) qui permet de ranker une grille (associer chaque grille à un entier) et unranker (obtenir la grille associée à un entier) sans passer par un fichier ; un peu à la manière dont on peut ranker et unranker une permutation ou une combinaison.

On pourrait pousser jusqu'à un 7×7, presque sans doublon avec un (ou plusieurs) filtres de bloom sans avoir à recourir à des entiers longs.

Hello,

Merci à tous pour vos réponses. Je vais explorer les différentes pistes et vous tiens au courant.

Edgar;