Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

executable file 738 lines (662 sloc) 22.066 kB
#!/usr/bin/python -Wall
# ================================================================
# This is a command-line program for doing some elementary computations on
# small finite groups: printing cayley tables, finding element orders and max
# orders, and so on. I wrote it in grad school, back in 2003-2005 or so, when
# I found my abstract-algebra courses to be just a little too abstract for my
# concrete tastes.
#
# ----------------------------------------------------------------
# You can use "sack --help" for on-line help:
#
# shell-prompt $ sack --help
# Usage: ./sack {group type} {command} {command arguments ...}
#
# Example: "./sack d:4 center ."
#
# Group types: T a ai cl2 d ispec metacyc modadd modmul pauli q q8 s si spec v4
#
# Commands: abelian add associative caytbl center close closed commutator
# conj_classes cyclic cycsgr cycsgrs derived elts eorder exp find_id
# has_inverses has_unique_id inverse inverses isgroup max_order mul nilpotent
# order orders solvable subgroup
#
# Your $PYTHONPATH should include the directory where you installed this file.
#
# ----------------------------------------------------------------
# The group types and commmands are listed above. To get information
# about the arguments needed for a particular command, omit them.
# For example:
#
# shell-prompt$ sack s:4 center
# center: 1 argument(s) needed; got 0.
#
# Most commands take a "." argument meaning "operate on all group elements".
# For example:
#
# (Center of dihedral group on four vertices)
# shell-prompt$ sack d:4 center .
# 0,0
# 2,0
#
# (All permutations on four points)
# shell-prompt$ sack s:4 elements .
# 1
# 1,4
# 1,3
# 1,2
# 2,4
# 2,3
# 3,4
# 1,4,3
# 1,4,2
# 1,3,4
# 1,3,2
# 1,2,4
# 1,2,3
# 2,4,3
# 2,3,4
# 1,4:2,3
# 1,3:2,4
# 1,2:3,4
# 1,4,2,3
# 1,4,3,2
# 1,3,2,4
# 1,3,4,2
# 1,2,4,3
# 1,2,3,4
#
# ----------------------------------------------------------------
# The input/output notation are more programmer-friendly than
# user-friendly; I wrote this program for myself to satisfy (in
# part) my preference for plain text I/O. Also, I intended this
# program to be self-educational; for information about how it
# works I tend to use the code itself as documentation.
#
# SACK does for small finite groups what RUFFL does for finite
# fields (https://github.com/johnkerl/ruffl).
#
# I don't expect too many people will find SACK useful -- on the
# other hand it might happen to be just what you're looking for.
# Enjoy!
#
# ================================================================
# Please see LICENSE.txt in the same directory as this file.
#
# John Kerl
# kerl.john.r@gmail.com
# 2007-05-31
# ================================================================
from __future__ import division # 1/2 = 0.5, not 0.
import sys
import re
# "Type" modules: for elements of various groups.
import dih_tm
import genquat_tm
import metacyc_tm
import modadd_tm
import modmul_tm
import pmti_tm
import pmtc_tm
import quatu_tm
import cl2_tm
import v4_tm
import T_tm
import pauli_tm
import spec_tm
import ispec_tm
#import semi_tm
# "Group" modules: for getting *all* elements of various groups.
import dn_gm
import qn_gm
import metacyc_gm
import modadd_gm
import modmul_gm
import sni_gm
import ani_gm
import snc_gm
import anc_gm
import quatu_gm
import cl2_gm
import v4_gm
import T_gm
import pauli_gm
import spec_gm
import ispec_gm
#import semi_gm
from sackset import *
from sackgrp import *
from sacktuple import *
# ----------------------------------------------------------------
# Short-hands for type names
type_lookup = {
"d" : dih_tm,
"q" : genquat_tm,
"metacyc" : metacyc_tm,
"modadd" : modadd_tm,
"modmul" : modmul_tm,
"q8" : quatu_tm,
"cl2" : cl2_tm,
"v4" : v4_tm,
"T" : T_tm,
"pauli" : pauli_tm,
"si" : pmti_tm,
"ai" : pmti_tm,
"s" : pmtc_tm,
"a" : pmtc_tm,
"spec" : spec_tm,
"ispec" : ispec_tm,
#"semi" : semi_tm,
}
# ----------------------------------------------------------------
# Short-hands for group names
group_lookup = {
"d" : dn_gm,
"q" : qn_gm,
"metacyc" : metacyc_gm,
"modadd" : modadd_gm,
"modmul" : modmul_gm,
"q8" : quatu_gm,
"cl2" : cl2_gm,
"si" : sni_gm,
"ai" : ani_gm,
"s" : snc_gm,
"a" : anc_gm,
"v4" : v4_gm,
"T" : T_gm,
"pauli" : pauli_gm,
"spec" : spec_gm,
"ispec" : ispec_gm,
#"semi" : semi_gm,
}
# ----------------------------------------------------------------
def main():
if (len(sys.argv) < 2):
short_usage(sys.argv[0])
if (sys.argv[1]=='help') or (sys.argv[1]=='-h') or (sys.argv[1]=='--help'):
long_usage(sys.argv[0])
# Examples:
# * d:4 denotes the dihedral group D4: dihedral family with parameter 4.
# * s:3 denotes S3.
# * spec:tbl.txt denotes a user-specified group with cayley table in file
# tbl.txt.
# * semi:V4/S3/action.txt denotes the semidirect product of V4 and S3 with
# the action of S3 on V4 in file action.txt. File format for N semi K:
# the file is a matrix with ith row and jth column being {n_i}^{k_j}.
type_and_group_params = re.split(':', sys.argv[1], 1);
type_name = type_and_group_params[0];
if (len(type_and_group_params) == 1) :
group_params_string = ""
else:
group_params_string = type_and_group_params[1]
if (not type_lookup.has_key(type_name)):
print "No such group type: " + type_name
sys.exit(1)
type_spec = type_lookup[type_name]
# Hack -- needs documentation. This is for defining ad-hoc groups
# from data files.
if (type_name == "spec" or type_name == "ispec"):
group_spec = group_lookup[type_name]
not_used = group_spec.get_elements_str(group_params_string)
# Hack -- needs documentation.
# * sys.argv[1] is "semi:v4/s:3/action.txt"
# * type_name is "semi"
# * group_params_string is "v4/s:3/action.txt"
# * Split on "/".
# * N_name is "v4"
# * K_name is "s:3"
# * aut_file_name is "action.txt"
#if (type_name == "semi") :
# [N_name, K_name, aut_file_name] = re.split('/', group_params_string, 2);
# Fill out N from N_name
# Fill out K from K_name
# Read in the action.txt matrix with values {n_i}^{k_j}, i.e. elements of
# N. This means we need to use N's I/O methods.
cmd_name = sys.argv[2];
if (not cmd_lookup.has_key(cmd_name)):
print "No such command: " + cmd_name
sys.exit(1)
handler = cmd_lookup[cmd_name]
cmd_argv = sys.argv[3:]
handler(cmd_name, cmd_argv, group_params_string, type_name, type_spec)
sys.exit(0)
# ----------------------------------------------------------------
def check_min_args(cmd_name, cmd_argv, n):
actual = len(cmd_argv)
if (actual < n):
print "%s: minimum %d argument(s) needed; got %d." % (
cmd_name, n, actual )
sys.exit(1)
# ----------------------------------------------------------------
def check_num_args(cmd_name, cmd_argv, n):
actual = len(cmd_argv)
if (actual != n):
print "%s: %d argument(s) needed; got %d." % (
cmd_name, n, actual )
sys.exit(1)
# ----------------------------------------------------------------
def group_from_file(type_spec, params_string, file_name):
G = []
if (file_name == "-"):
file_handle = sys.stdin
else:
try:
file_handle = open(file_name, 'r')
except:
print "Couldn't open \"" + file_name + "\" for read."
sys.exit(1)
for line in file_handle:
if (line[-1] == '\n'):
line = line[0:-1]
x = type_spec.from_string(line, params_string)
G.append(x)
if (file_name != "-"):
file_handle.close()
return G
# ----------------------------------------------------------------
def get_group(type_name, group_params_string, file_name):
if (file_name == "."):
if (not group_lookup.has_key(type_name)):
print "No such full group: " + type_name
sys.exit(1)
group_spec = group_lookup[type_name]
G = group_spec.get_elements_str(group_params_string)
else:
G = group_from_file(type_spec, group_params_string, file_name)
return G
# ----------------------------------------------------------------
# E.g. "sack s:4 mul 1,2,4 2,3,1" prints "1,4:2,3".
def cmd_mul(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_min_args(cmd_name, cmd_argv, 1)
x = type_spec.from_string(cmd_argv[0], group_params_string)
for arg in cmd_argv[1:]:
y = type_spec.from_string(arg, group_params_string)
x = x * y
print x
# ----------------------------------------------------------------
def cmd_add(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_min_args(cmd_name, cmd_argv, 1)
x = type_spec.from_string(cmd_argv[0], group_params_string)
for arg in cmd_argv[1:]:
y = type_spec.from_string(arg, group_params_string)
x = x + y
print x
# ----------------------------------------------------------------
def cmd_close(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
close_group(G)
print_set_as_column(G)
# ----------------------------------------------------------------
def cmd_exp(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_min_args(cmd_name, cmd_argv, 2)
# xxx try: except:
e = int(cmd_argv[-1])
for arg in cmd_argv[0:-1]:
x = type_spec.from_string(arg, group_params_string)
y = sackexp(x, e)
print y
# ----------------------------------------------------------------
# E.g. "sack s:4 inverse 1,2,3,4" prints "1,2,3,4 1,4,3,2"
def cmd_inverse(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_min_args(cmd_name, cmd_argv, 1)
for arg in cmd_argv:
x = type_spec.from_string(arg, group_params_string)
y = x.inv();
print x, y
# ----------------------------------------------------------------
def cmd_commutator(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_min_args(cmd_name, cmd_argv, 1)
argc = len(cmd_argv)
if (argc == 2):
x = type_spec.from_string(cmd_argv[0], group_params_string)
y = type_spec.from_string(cmd_argv[1], group_params_string)
xi = x.inv()
yi = y.inv()
bracket = x * y * xi * yi
print bracket
else:
print "commutator: needed 2 elements; got %d." % (argc)
sys.exit(1)
# ----------------------------------------------------------------
def cmd_eorder(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_min_args(cmd_name, cmd_argv, 1)
for arg in cmd_argv:
x = type_spec.from_string(arg, group_params_string)
k = get_order(x)
print x, k
# ----------------------------------------------------------------
def cmd_cycsgr(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_min_args(cmd_name, cmd_argv, 1)
for arg in cmd_argv:
x = type_spec.from_string(arg, group_params_string)
pig = get_cycsgr(x)
#print_set_as_row(pig)
print_set_as_column(pig)
print
# ----------------------------------------------------------------
def cmd_elts(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
print_set_as_column(G)
# ----------------------------------------------------------------
# E.g. "sack s:3 caytbl ."
def cmd_caytbl(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
print_cayley_table(G)
# ----------------------------------------------------------------
def cmd_conj_classes(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
print_conj_classes(G)
# ----------------------------------------------------------------
def cmd_find_id(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
[found, e] = find_id(G)
if (found):
print e
else:
print "No identity found"
# ----------------------------------------------------------------
# E.g. "sack s:4 order ." prints 24.
def cmd_order(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
print len(G)
# ----------------------------------------------------------------
# E.g. "sack s:4 orders . | left" prints
#
# 1 1
# 1,4 2
# 1,3 2
# 1,2 2
# 2,4 2
# 2,3 2
# 3,4 2
# 1,4,3 3
# 1,4,2 3
# 1,3,4 3
# 1,3,2 3
# 1,2,4 3
# 1,2,3 3
# 2,4,3 3
# 2,3,4 3
# 1,4:2,3 2
# 1,3:2,4 2
# 1,2:3,4 2
# 1,4,2,3 4
# 1,4,3,2 4
# 1,3,2,4 4
# 1,3,4,2 4
# 1,2,4,3 4
# 1,2,3,4 4
def cmd_orders(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
orders = get_orders(G)
n = len(G)
for k in range(0, n):
print G[k], orders[k]
# ----------------------------------------------------------------
# E.g. "sack s:4 max_order ." prints 4.
def cmd_max_order(cmd_name, cmd_argv, group_params_string, type_name,type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
m = get_max_order(G)
print m
# ----------------------------------------------------------------
# E.g. "sack s:4 inverses . | left" prints
# 1 1
# 1,4 1,4
# 1,3 1,3
# 1,2 1,2
# 2,4 2,4
# 2,3 2,3
# 3,4 3,4
# 1,4,3 1,3,4
# 1,4,2 1,2,4
# 1,3,4 1,4,3
# 1,3,2 1,2,3
# 1,2,4 1,4,2
# 1,2,3 1,3,2
# 2,4,3 2,3,4
# 2,3,4 2,4,3
# 1,4:2,3 1,4:2,3
# 1,3:2,4 1,3:2,4
# 1,2:3,4 1,2:3,4
# 1,4,2,3 1,3,2,4
# 1,4,3,2 1,2,3,4
# 1,3,2,4 1,4,2,3
# 1,3,4,2 1,2,4,3
# 1,2,4,3 1,3,4,2
# 1,2,3,4 1,4,3,2
def cmd_inverses(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
for x in G:
y = x.inv()
print x, y
# ----------------------------------------------------------------
# E.g. "sack s:4 center ." prints 1 (only the identity permutation commutes
# with all other permutation.
def cmd_center(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
Z = get_center(G)
print_set_as_column(Z)
# ----------------------------------------------------------------
def cmd_isgroup(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
if (is_group(G)):
print "is a group"
else:
print "not a group"
# ----------------------------------------------------------------
def cmd_closed(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
if (is_closed(G)):
print "closed"
else:
print "non-closed"
# ----------------------------------------------------------------
def cmd_associative(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
if (is_associative(G)):
print "associative"
else:
print "non-associative"
# ----------------------------------------------------------------
def cmd_has_unique_id(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
if (has_unique_id(G)):
print "has unique identity"
else:
print "does not have unique identity"
# ----------------------------------------------------------------
def cmd_has_inverses(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
if (has_inverses(G)):
print "has inverses"
else:
print "does not have inverses"
# ----------------------------------------------------------------
# E.g. "sack s:4 cyclic ." prints "non-cyclic"; "sack modadd:4 cyclic ." prints "cyclic".
def cmd_cyclic(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
if (is_cyclic(G)):
print "cyclic"
else:
print "non-cyclic"
# ----------------------------------------------------------------
# E.g. "sack s:4 abelian ." prints "non-abelian"; "sack modadd:4 abelian ." prints "abelian".
def cmd_abelian(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
if (is_abelian(G)):
print "abelian"
else:
print "non-abelian"
# ----------------------------------------------------------------
def cmd_nilpotent(cmd_name, cmd_argv, group_params_string, type_name,type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
if (is_nilpotent(G)):
print "nilpotent"
else:
print "non-nilpotent"
# ----------------------------------------------------------------
def cmd_solvable(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
if (is_solvable(G)):
print "solvable"
else:
print "non-solvable"
# ----------------------------------------------------------------
def cmd_derived(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
G1 = derived_subgroup(G)
print_set_as_column(G1)
# ----------------------------------------------------------------
def cmd_cycsgrs(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 1)
G = get_group(type_name, group_params_string, cmd_argv[0])
for x in G:
pig = get_cycsgr(x)
print_set_as_row(pig)
# ----------------------------------------------------------------
def cmd_subgroup(cmd_name, cmd_argv, group_params_string, type_name, type_spec):
check_num_args(cmd_name, cmd_argv, 2)
G = get_group(type_name, group_params_string, cmd_argv[0])
H = get_group(type_name, group_params_string, cmd_argv[1])
if (not subset_of(H, G)):
print "Not a subset."
elif (not is_group(H)):
print "Not a subgroup."
else:
print "Is a subgroup."
# ----------------------------------------------------------------
cmd_lookup = {
"mul" : cmd_mul,
"add" : cmd_add,
#"sub" : cmd_sub,
#"quot" : cmd_quot,
#"rem" : cmd_rem,
"close" : cmd_close,
"exp" : cmd_exp,
"inverse" : cmd_inverse,
"commutator" : cmd_commutator,
"eorder" : cmd_eorder,
"cycsgr" : cmd_cycsgr,
"elts" : cmd_elts,
"caytbl" : cmd_caytbl,
"conj_classes" : cmd_conj_classes,
"find_id" : cmd_find_id,
"order" : cmd_order,
"orders" : cmd_orders,
"max_order" : cmd_max_order,
"inverses" : cmd_inverses,
"center" : cmd_center,
"isgroup" : cmd_isgroup,
"closed" : cmd_closed,
"associative" : cmd_associative,
"has_unique_id": cmd_has_unique_id,
"has_inverses" : cmd_has_inverses,
"cyclic" : cmd_cyclic,
"abelian" : cmd_abelian,
"nilpotent" : cmd_nilpotent,
"solvable" : cmd_solvable,
"derived" : cmd_derived,
"cycsgrs" : cmd_cycsgrs,
"subgroup" : cmd_subgroup,
}
# ----------------------------------------------------------------
def short_usage(argv0):
print "Usage: " + argv0 + " {group type} {command} {command arguments ...}"
print "Please type \"" + argv0 + " --help\" for detailed help."
sys.exit(1)
# ----------------------------------------------------------------
def long_usage(argv0):
print "Usage: " + argv0 + " {group type} {command} {command arguments ...}"
print
print "Example: \"" + argv0 + " d:4 center .\""
print
print "Group types:",
group_types = type_lookup.keys()
group_types.sort()
for k in group_types:
print k,
print
print
print "Commands:",
cmd_names = cmd_lookup.keys()
cmd_names.sort()
for k in cmd_names:
print k,
print
print
sys.exit(1)
# ================================================================
# Script entry point (top-down programming style, please).
main()
# ================================================================
# To do:
# * from_file stuff
# * sack d center .: give usage
# * __lt__ et al. everywhere
# * deepsort method -- into sackset? use this post-close.
# * dih 1:0 vs. 1,0 -- fix error handling
# * pmt sgn method: bubble sort w/ swap count
# Commands to implement:
# * centralizer
# * conjbyelt
# * conj_classes
# * cosets L/R
# * internal dp
# * is_subgroup
# * normalizer
# * normal_subgroup
# * powsgr
# * torsion
# * ascendant
# * aut_group
# * cap
# * cayley_sn
# * core
# * cosets
# * inn
# ----------------------------------------------------------------
# Groups:
# * sn an sni ani
# * fpell3 ftell5
# * triv testing smodadd smodmul miquatadd miquatmul smiquatadd smiquatmul
# * z2ipolymodadd z2ipolymodmul zppolyadd zppolymul tetra cube icos slgf glgf dgf
# ----------------------------------------------------------------
# ring stuff -- ops, at least
# kalk-like interface
# ----------------------------------------------------------------
# Wreath product -- !
# ----------------------------------------------------------------
# Incorporate:
# * PMATLIB, all
# * SPFFL, all
# - have a single poly class
# - have a single mod class
# - have a single rat class
# - have a single matrix class. methods from PMATLIB & tmatrix.h.
# - tmvpoly
# * kbc, with Python eval?
# * kalk
# * groebner:
# - generalized division alg'm
# * new & improved aut-group computation (need generators)?
# ================================================================
Jump to Line
Something went wrong with that request. Please try again.