Je voudrais compter le nombre de matrices M de N dont les éléments sont 1 ou -1 ont la propriété que tous ses Plancher (M / 2) +1 par N code> Les sous-manières ont un rang complet. Ma méthode actuelle est naïve et lente et est dans le code Python / Numpy suivant. Il s'agit simplement de toutes les matrices et teste toutes les submatures. import numpy as np
import itertools
from scipy.misc import comb
m = 8
n = 4
rowstochoose = int(np.floor(m/2)+1)
maxnumber = comb(m, rowstochoose, exact = True)
matrix_g=(np.array(x).reshape(m,n) for x in itertools.product([-1,1], repeat = m*n))
nofound = 0
for A in matrix_g:
count = 0
for rows in itertools.combinations(range(m), int(rowstochoose)):
if (np.linalg.matrix_rank(A[list(rows)]) == int(min(n,rowstochoose))):
count+=1
else:
break
if (count == maxnumber):
nofound+=1
print nofound, 2**(m*n)
4 Réponses :
Puisque personne n'est répondu pour le moment, voici une réponse sans code. Les symétries utiles que je vois sont les suivantes.
J'attaquerais ce problème par générer de manière exhaustive les non-isomorphes , les filtrant et résumant les tailles de leurs orbites. Nauty sera très utile pour les première et troisième étapes. En supposant que la plupart des matrices ont peu de symétries (sans aucun doute une excellente hypothèse de N gros, mais ce n'est pas évident une priori à quel point), je m'attendrais à ce que 8x8 soit faisable, 9x9 soit limite, et 10x10 pour être hors de portée.
pseudocode expansé:
générer un représentant de chaque orbite des (M-1) par (n-1) 0-1 matrices agitées par le groupe généré par des permutations de rangée et de colonne, ainsi que la taille de l'orbite (= (M - 1)! (N - 1)! / La taille du groupe automorphisme). L'auteur de l'article que Tim liked serait peut-être disposé à partager son code; Sinon, voir ci-dessous.
pour chaque matrice, remplacez les entrées x par (-1) ^ x. Ajoutez une ligne et une colonne de 1s. Multipliez la taille de son orbite par 2 ^ (m + n - 1). Cela prend en charge les symétries de changement de signe.
Filtrez les matrices et résumez les tailles d'orbite de celles qui restent. Vous pouvez économiser un peu de temps de calcul ici en implémentant Gram - Schmidt vous-même afin que lorsque vous essayez toutes les combinaisons dans l'ordre lexicographique, il est possible de réutiliser des résultats partiels pour les préfixes partagés.
Enumération sans isomorphe:
Modèle de McKay peut être utilisé pour générer les représentants de (M + 1) par N 0-1 Matrices des représentants des MS par N 0-1 Matrices, de manière à une première recherche de profondeur. Avec chaque m de n 0-1 matricielle, associez un graphique bipartite avec des sommets noirs, n sommets blanches et le bord approprié pour chaque entrée. Faites ce qui suit pour chaque M par N représentatif.
pour chaque vecteur Longueur-N, construisez le graphique pour la matrice (M + 1) par N matricielle composée du représentant avec le nouveau vecteur et exécutez Nauty pour obtenir un étiquetage canonique et les orbites de sommet.
Filtrez les possibilités où le sommet correspondant au nouveau vecteur est dans une orbite différente du sommet noir avec le nombre le plus bas.
Filtrez les possibilités avec des étiquettes canoniques en double.
Nauty calcule également les commandes de groupes automorphisme.
Pour la contraste, Classification des petites matrices (0,1) Matrices Détails Algorithmes utilisés pour le " Plus simple "(espace de recherche plus petit) tâche de classification (0,1) nxn matrices de différentes manières. 8x8 a été faisable à l'auteur, mais nécessitait un mois de calcul sur 5 pcs; Il estime que terminer 9x9 prendrait 1000 fois plus de temps. Là encore, les classifications qu'il a eu l'air plus difficile que celle-ci. En tout cas, ce n'est pas vraiment une programmation question - ce qui est vraiment nécessaire ici est une analyse approfondie.
@ Typimètres Les panneaux de retournement nous donnent efficacement une rangée et une colonne de "Gratuit", de sorte que le cas de 8x8 de ce problème correspond au cas 7x7 de celui-là.
Otoh, le nombre de matrices non confortables 2 ** (2 * n-1) fois le nombre de non-singulaires (n- 1) x (n-1) {0, 1} matrices. Peu importe la façon dont vous coupez cela, il y a des "lots" de 'em ;-) Voir "Nombre de non confondus N x N (- 1,1) -Matrices. ".
Merci pour votre réponse. Pourriez-vous éventuellement élargir le pseudocode afin que quelqu'un puisse essayer de voir comment implémenter votre idée?
@Marshall s'est développé autant que j'ai le temps de voir maintenant. Ceci est un peu délicat à mettre en œuvre, mais cela fonctionne pour cette question, votre autre, et d'autres personnes à part que vous pourriez avoir à l'avenir.
@TimPeters Je pense que nous parlons les uns des autres. Oui, il y a beaucoup de 7 par 7 matrices avec 0-1 entrées. Je ne propose pas de les énumérer tous, un seul représentant de chacun des orbites du groupe de symétrie, qui devrait être numéro de cent millions. Le truc d'exclusion d'inclusion que j'ai sorti la dernière fois semble non-consistant car le nombre de sous-espaces de colonne va être beaucoup plus grand.
J'utiliserais la mémorisation des matrices plus petites déjà vérifiées.
Vous pouvez simplement écrire en format binaire (0 pour -1, 1 pour 1) toutes les matrices plus petites. BTW, vous recherchez directement les matrices de gammes de (0 et 1) au lieu de (-1 et 1) - c'est la même chose. Appelons ces images codantes. En utilisant des types de longs, vous pouvez avoir des matrices allant jusqu'à 64 cellules, jusqu'à 8x8. C'est rapide. Utiliser une chaîne, vous pouvez leur avoir aussi grand que nécessaire. Vraiment, 8x8 est plus que suffisant - dans la mémoire de 8 Go, nous pouvons placer 1G Longs. Il est environ 2 ^ 30, vous pouvez donc vous rappeler des matrices d'environ 25-28 éléments.
Pour chaque taille, vous aurez un ensemble d'images:
pour 2x2: 1001, 0110, 1000, 0100, 0010, 0001, 0111, 1011, 1101, 1110.
Alors, vous aurez L'autre possibilité est de créer des matrices plus grandes en ajoutant des pièces aux moindreités, déjà trouvées.
Vous devriez décider, jusqu'à quelle taille les matrices vont grandir.
Lorsque vous trouvez une matrice "correcte" de taille MXN, essayez d'ajouter une ligne au sommet. Les nouvelles matrices doivent être cochées uniquement pour les sous-matières qui incluent la nouvelle ligne. La même chose avec la nouvelle colonne.
Vous devez définir un algorithme exact, quelles tailles sont dérivées des quelles tailles. Ainsi, vous pouvez minimiser le nombre de matrices mémorisées. J'ai pensé à cette séquence:
Vous pouvez donc vous rappeler que (m + n) / 2-1 matrices pour rechercher parmi les tailles MXN.
Si chaque fois que nous pourrons créer une nouvelle taille de deux anciens, nous découlons de plus en plus carrés, nous pourrions aussi beaucoup de réserve pour les matrices en mémoire: pour les matrices «longues» comme 7x2, nous avons besoin de vous souvenir et de vérifier que le dernier ligne 1x2. Pour les matrices 6x3, nous devrions nous rappeler leur talon de 2x3, et ainsi de suite.
En outre, vous n'avez pas besoin de vous rappeler les plus grandes matrices - vous ne les utiliserez pas pour le comptage ultérieur.
Utilisez à nouveau des "images" pour mémoriser la matrice. archive = tableau de NXN, dont chaque élément sera une liste ordonnée d'images binaires de bonnes matrices.
- (pour la taille matricielle MXN, où M> = N, l'endroit approprié dans les archives aura des coordonnées M, n. Si m
Algorithme 2 - Augmentation des tailles
Je trouve cette réponse un peu déroutant. Si vous pouviez afficher un certain code qui fonctionne pour les petites n et m explicitement, je peux le tester pour voir si cela donne les réponses que je m'attends.
(Maintenant une solution partielle pour n = m // 2 + 1, et le code demandé.)
let k: = m // 2 + 1 p>
C'est un peu équivalent à demander , "Combien de collections de vecteurs M N-dimensionnels de {-1,1} n'ont pas de jeux de taille minière linéairement dépendants (k, n)?" P>
pour ces matrices, nous savons ou pouvons supposer: p>
Avec cela, nous avons une solution pour n = 4, m = 8. Il n'y a que huit vecteurs différents avec la propriété que la première entrée est positive. Il n'y a qu'une seule combinaison (liste triée) de 8 vecteurs distincts de 8 vecteurs distincts. P>
import numpy as np
from numpy import unpackbits, arange, uint8, int8, array
from itertools import combinations
#all distinct n-length vectors from -1,1 with first entry -1
def nvectors(n):
if n > 8:
raise ValueError #is that the right error?
if n==0:
return array([])
return -1 + 2 * (
#explode binary numbers to arrays of 8 zeroes and ones
unpackbits(arange(2**(n-1),dtype=uint8)) #unpackbits only takes uint
.reshape((-1,8)) #unpackbits flattens, so we need to shape it to 8 bits
[:,-n:] #only take the last n bytes
.view(int8) #need signed
)
#generate all length-m matrices that are combinations of distinct n-vectors
def matrix_g(n,m):
return (array(mat) for mat in combinations(nvectors(n),m))
rankof = np.linalg.matrix_rank
#all submatrices of at least half size have maxrank
#(we only need to check the maxrank-sized matrices)
def halfrank(matrix,maxrank):
return all(rankof(submatr) == maxrank for submatr in combinations(matrix,maxrank))
#generate all matrices that have all half-matrices with full rank
def nicematrices(m,n):
maxrank = min(m//2+1,n)
return (matr for matr in matrix_g(n,m) if halfrank(matr,maxrank))
#returns (number of nice matrices, number of all matrices)
def count_nicematrices(m,n):
from math import factorial
return (len(list(nicematrices(m,n)))*factorial(m)*2**m, 2**(m*n))
for i in range(0,6):
print (i, count_nicematrices(i,i))
J'ai supprimé cette ligne sur le cas 8x4: "Cette matrice a un rang complet, donc chaque sous-pilote doit avoir un rang complet." C'est faux.
Résolu pour n> = m // 2 + 1 .
Qu'est-ce que vous obtenez pour n, m = 5,5?
4,4: 26880. 5,5: 16773120. 6,6: 41757327360. Donc, évidemment, ma réponse est erronée en ce moment.
Je pense que je suis faible mais pourquoi est-ce évidemment faux?
Ma réponse a déclaré que N> = m // 2 + 1 n'avait aucune solution, mais j'ai compté plus que cela.
Ajout du code de comptage. Devrait travailler à la fois python 2 et python 3
Pour N = 2 et M = 2,3,4,5,6 Les sorties doivent être de 8, 0, 96, 0, 1280. Je ne comprends pas cela avec votre code.
Quelle matrice de 2 coordonnées {-1,1} a six rangées où chaque ensemble de trois rangées a rang 2?
Nous avons besoin de chaque ensemble de 6/2 + 1 = 4 rangées pour avoir le rang 2. [[[-1 -1] [-1 -1] [-1 -1] [-1 1] [-1 1] [-1 1]]
... Eh bien. Ce n'est pas une solution facile. J'y penserai demain.
vous doit repenser ce problème d'un point de vue mathématique. Cela dit même avec une force brute, il y a des astuces de programmation que vous pouvez utiliser pour accélérer le processus (comme un site de programmation). Peu d'astuces comme ne pas recalculer ceci donne un gain de vitesse de presque 10x pour le boîtier 4x4 - vous verrez Des améliorations substantielles pour des matrices plus importantes si vous souhaitez attendre assez longtemps. Il est possible pour les principales matrices, où le coût du rang est proportionnellement plus cher, que vous pouvez commander les matrices à l'avance à l'avance sur le hachage: pour le boîtier 4x4 Cela le rend légèrement pire, mais je m'attends à ce que cela reverse pour le cas 5x5. int (min (n, rowschoose)) et itTools.combinations (gamme (m), int (Rowstochoose)) peut économiser quelques pour cent - mais Le vrai gain provient de la mémoisation. D'autres l'ont mentionné, mais je pensais qu'il pourrait être utile d'avoir un exemple complet, de travail, de code:
Remplacer normalement Linalg.Matrix_Rank de Linalg.Det serait également différent de manière différente, car il est beaucoup plus rapide de calculer le déterminant que le rang d'une matrice. Cependant, je ne vois pas comment faire ça ici.
@Marshall qui nécessite que vous ayez une matrice carrée - ce n'est pas vrai en général pour votre problème.
@Marshall Votre meilleur pari à ce jour ressemble à une combinaison de mémoisation et de la matrice réduite générée par la réponse de Leewangzhong.
@Teeheemm bon point. Merci.
Plus tôt, vous avez dit que vous aviez besoin de cela pour une simulation; Cela n'a aucun sens pour moi, mais peu importe, nous pourrions aller au cœur de la question plus rapidement si vous nous l'avez dit un peu plus sur ce que vous essayez réellement de réaliser.
Notez que la grade de matrice et les paires de lignes résument à la même valeur, ne sont pas la même chose. Pas ça me dérange; Ils sont tous des problèmes intéressants pour moi. Mais si c'est le premier que vous êtes intéressé, vous auriez pu vous enregistrer beaucoup de temps en donnant un certain temps plus de contexte.
@Eelcohoogendoorn Cette question est complètement indépendante à toute autre question que j'ai posée. J'ai ajouté du contexte à la question.
Il est plutôt directement lié à votre question concernant des paires de paires de lignes qui somme à la même valeur. Votre lien semble vous suggérer que vous êtes intéressé par la question pour son propre saké, ce qui signifie qu'il n'est pas question de demander quel est votre problème réel, et si nous ne devons pas essayer de prendre un pas en arrière afin de le résoudre. Est-ce exact?
@Eelcohoogendoorn Mon intérêt ici est vraiment dans le problème de mathématiques lié pour son propre saké. Je ne sais pas comment obtenir une réponse exacte pour cela et si vous regardez la réponse, il est également approximatif. J'espérais calculer des réponses exactes pour les petites n et m.
Ne devriez-vous pas comparer le rang à
min (n, rowschoose) ? Le plus grand rang possible d'unJXK matrice estmin (j, k) , et je suppose que c'est ce que vous entendez par "rang complet".@TimPeters merci pour ce correctif.
Je me demande si une approche dynamique aiderait? Si les deux premières lignes sont les mêmes (par exemple), alors chaque fois que vous choisissez ces lignes, la matrice n'aura pas au total. Mais il y aurait toujours une quantité massive de matrices pour examiner. Peut-être que la voie à suivre serait de générer les soumissions du rang complet et de compter combien de matrices ont ces soumissions (mais en surveillant la sur-compte).
Avez-vous remarqué que
matrix_g génère 2 ^ 32 éléments?J'ai vérifié un million de matrices aléatoires (avec des lignes distinctes et une première coordonnée -1) pour n = 8 et m = 8 et aucun d'entre eux n'avait de sous-pilation de rang inférieur à 5.
@lewangzhong Re: matrix_g. Oui mon code est terrible :)
Réponse à EDIT: Ouais, mon hypothèse de base sur le caractère unique des vecteurs de la liste ne contient pas de k plus gros que N, mais je ne sais pas combien de plus. Pour K> N, vous pouvez prendre toutes les combinaisons de vecteurs avec repick autorisé ( docs.python.org/2/library/... ), mais Ugh, c'est terrible (bien que ce soit plus rapide que l'original, peut-être).