Haskellのランダムについて

Hakellは関数型言語で参照透過性とかを保証するために、同じことをやったら同じ結果が出ることが保証されているために、randomについてはちょっとというか相当ややこしい。


いまの私の理解は以下のようなものですが、これで合ってるか。

 

import System.Random
let dice=do;n<-getStdRandom(randomR(1,6::Int));return n

 

として、diceと打ち込むと1から6の範囲でランダムに数字を返してくれるので一見ランダムに見える。
がしかし、これは数字でないのでそのままでは使い物にならない。

 

dice + 3 -- > errorになる
n = dice -- > errorになる

 

タイプを調べてみると

 

:t dice -- > IO Int

 

となって、ただのIntに変換するためには一旦再度IOを通す必要がある。

 

n <- dice

 

とすると数字になる。


リストにしてみたらどうか。

import Control.Monad
replicateM 10 $ getStdRandom(randomR(1,6::Int))
-- > [5,6,5,4,4,2,3,5,1,6]

 

とかも IO [Int]なので、sumすることもできない。sumするためには

 

list <- replicateM 10 $ getStdRandom(randomR(1,6::Int))
list -- > [1,6,6,3,6,2,4,3,5,2]
sum list -- > 38


ということ。


Haskellは同じランダムのたねを入れるとランダムの返す値が同じになる。
なので、setStdGenで毎回同じタネを入れると同じランダム値になってしまう。

 

setStdGen(mkStdGen 12)
getStdRandom(randomR(0, 1.0))
0.13293852220286906
setStdGen(mkStdGen 12)
getStdRandom(randomR(0, 1.0))
0.13293852220286906

 

getStdGenで生成するStdGenは起動時にセットされたものを返してくるので、使うたびにStdGenを書き換えるnewStdGenとか、getStdRandomを使う必要がある。

 

getStdGenを使うとこんな感じです。ランダムな値が全部同じになってしまいます。
gen <- getStdGen
take 10 $ randomRs (1,6) gen
[1,6,5,1,3,5,6,5,5,4]
take 10 $ randomRs (1,6) gen
[1,6,5,1,3,5,6,5,5,4]
gen <- getStdGen
take 10 $ randomRs (1,6) gen
[1,6,5,1,3,5,6,5,5,4]

 

newStdGenを使うと次のように毎回違った値になりますが、やはり毎回呼び出す必要がある。


gen <- newStdGen
take 10 $ randomRs (1,6) gen
[4,1,3,3,4,2,3,2,6,4]
gen <- newStdGen
take 10 $ randomRs (1,6) gen
[5,2,4,2,3,3,3,5,1,6]
gen <- newStdGen
take 10 $ randomRs (1,6) gen
[1,2,2,2,4,3,3,4,3,3]
gen <- newStdGen
take 10 $ randomRs (1,6) gen
[3,1,1,3,5,1,5,5,6,6]

 

これだとIO Intではなくてただのリスト[Int]なので扱いは楽です。

 

ラムダ式にくるんで、ひとつの関数内でIO IntからIntにできないかと考えたのですが、できませんでした。できたら関数プログラミングでなくなってしまう。かも。

 

いまの結論:


newStdGenを使う。毎回呼び出す。gen <- newStdGen。
randomRsを使う。

 

問題1: '0123456789ABCDEEFGHIJKLMNOPQRSTUVWXYZ'内の文字をランダムに並べる。
問題2: 'あいうえおかきくけこさしすせそたちつてとなにぬねのはひふへほまみむめもやゆよらりるれろわゐゑをん'をランダムに用いて5,7,5の俳句をつくる。

 

問題1: 解答例

-- random36.hs
-- runghc rndom36.hs

import System.Random
import Data.List
import Control.Monad

main :: IO ()
main = do
    gen <- newStdGen
    let randomlist = take 30 $ randomRs (0,35::Int) gen
    let result = map (str!!) randomlist
    putStrLn result

str="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

 -- 出力例

Z8CIZZB9OTO6RDTHI2YW0A0LN9RFU2
R6PZKKZ4MVJFKI8ALNU7GGWXB48987

 

 

問題2: 解答例

-- randomhaiku.hs
-- runghc randomhaiuku.hs

import System.Random
import Data.List
import Control.Monad

main :: IO ()
main = do
    gen <- newStdGen
    let first = map (str!!) $ take 5 $ randomRs (0, 47::Int) gen
    gen <- newStdGen
    let second = map (str!!) $ take 7 $ randomRs (0, 47::Int) gen
    gen <- newStdGen
    let third = map (str!!) $ take 5 $ randomRs (0, 47::Int) gen
    let result = unwords [first, second, third]
    putStrLn result

str="あいうえおかきくけこさしすせそたちつてとなにぬねのはひふへほまみむめもやゆよらりるれろわゐゑをん"

-- 作品例
-- やふるれな えかねもひんは よゆいのて
-- はゐへおき れつしゐきによ ぬきよるお
-- ゆんのしは おはすおはねせ らそむあね
-- ねろれすと りなのかとおな なえうわつ
-- ゆつゆのき おらとちすへち らふゑすお
-- りんうなあ くとりせきはり ゆこさけを
-- いははつろ つえけころれや をももかる
-- ぬんみやい らなとへいゐや とこゑねれ
-- やあなもも おふえふもりれ むちほつひ
-- ゑとしゐろ せをあよろめか んやとむる
-- ねかもはさ りみねてさやゆ はたろせう
-- むそうへめ いもらにりとけ ほのさちみ
-- むみうおわ いえりゐわなり ほれさるや
-- わほゆうみ しいはわみきと ゑりえりほ
-- ねうぬへん りへかにんころ はすみちゑ
-- てえならち もほえみちろう たてほひそ

 

 

Ubuntuのマウスポインターを大きくする

マウスのポインターを大きくする方法です。

 

目が悪くなってきたのと、起動時に無線マウスの反応が悪くて、マウスの矢印がすこしでも大きいといいかな、と思い探してやってみました。うまく行ったのでご報告。

 

環境はUbuntu 16.04です。

 

echo "Xcursor.size: 48" | tee ~/.Xresources
gsettings set com.canonical.Unity.Interface cursor-scale-factor 2

この方法だと再起動しても元に戻らない。

 

先日書いた方法(deconf-tools)では、再起動するともとにもどってしまうので、 記事を書き換えました。

 

以上

 

SageMathとグラフ理論(オイラーの公式)

問題

 

車輪グラフW_{8}ついて、オイラーの公式(Euler's formula)が成り立つことを確認せよ。

 

オイラーの公式:

$$ n - m + f = 2 $$

n: 頂点の数、m: 辺の数、f: 面の数

f:id:niming538:20171009133810p:plain

 

 

%hist
G=graphs.WheelGraph(8)
show(G)
len(list(G.vertex_iterator())) # -> 8
len(list(G.edge_iterator())) # -> 14
len(G.faces()) # -> 8
n, m , f = 8, 14, 8
n - m + f == 2 # -> True

アイデア: エレキギターハンガー

ダイソー 車のシートフック

 

という自動車のヘッドレストのポールにつける二連のフックがあります。

 

これがギターハンガーにならないか、というアイデアです。

みかけはギターハンガーにそっくりです。

 

とりあえず買ってきて、合わせてみたところ自分のエレキギターには間がほんのすこし広すぎるみたいなので、工夫中。

 

だれかやってみた人いないかな。

 

f:id:niming538:20171006205350j:plain

SageMathでグラフ理論(TABの使い方)

SageMathでグラフに関係してどんな関数があるか、とか調べるときにタブ補完(Tab completion)を使います。


たとえば、グラフを書きたいとき、

 

G=graphs.<TAB>

 

と押すと、200個ほどの関数がある。

また、G=Graph()としたうえで、

 

G.<TAB>

 

と押すと、グラフに使える関数が300個以上あります。

 

これが一覧性がなくて、マニュアルに一覧表もないようなので、コピペで作ってみました。

 

参考のために作り方ですが、端末(ターミナル)をできるだけ上下左右に大きくとります。端末の範囲内で一覧表示をするので、clearしたうえで<TAB>を使えばたいていの場合、一覧できると思います。今回のように数百あって、何ページかにまたがる場合は、テキストエディターにコピペして、ソートして、コピペの際に生じた重複を消すなどの作業をします。私の場合、Haskellでやりました。

 

contents <- readFile "graphs_tab.txt"
writeFile "graphs_tab02.txt" $ unlines $ nub $ sort $ words contents

みたいな感じ。

 

さて、G=graphs.<TAB>の結果とG.<TAB>の結果です。


graphs.AffineOrthogonalPolarGraph
graphs.AhrensSzekeresGeneralizedQuadrangleGraph
graphs.Balaban10Cage
graphs.Balaban11Cage
graphs.BalancedTree
graphs.BarbellGraph
graphs.BidiakisCube
graphs.BiggsSmithGraph
graphs.BishopGraph
graphs.BlanusaFirstSnarkGraph
graphs.BlanusaSecondSnarkGraph
graphs.BrinkmannGraph
graphs.BrouwerHaemersGraph
graphs.BubbleSortGraph
graphs.BuckyBall
graphs.BullGraph
graphs.ButterflyGraph
graphs.CameronGraph
graphs.Cell120
graphs.Cell600
graphs.ChessboardGraphGenerator
graphs.ChvatalGraph
graphs.CirculantGraph
graphs.CircularLadderGraph
graphs.ClawGraph
graphs.ClebschGraph
graphs.CompleteBipartiteGraph
graphs.CompleteGraph
graphs.CompleteMultipartiteGraph
graphs.CossidentePenttilaGraph
graphs.CoxeterGraph
graphs.CubeGraph
graphs.CycleGraph
graphs.DegreeSequence
graphs.DegreeSequenceBipartite
graphs.DegreeSequenceConfigurationModel
graphs.DegreeSequenceExpected
graphs.DegreeSequenceTree
graphs.DejterGraph
graphs.DesarguesGraph
graphs.DiamondGraph
graphs.DodecahedralGraph
graphs.DorogovtsevGoltsevMendesGraph
graphs.DoubleStarSnark
graphs.DurerGraph
graphs.DyckGraph
graphs.EllinghamHorton54Graph
graphs.EllinghamHorton78Graph
graphs.EmptyGraph
graphs.ErreraGraph
graphs.F26AGraph
graphs.FibonacciTree
graphs.FlowerSnark
graphs.FoldedCubeGraph
graphs.FolkmanGraph
graphs.FosterGraph
graphs.FranklinGraph
graphs.FriendshipGraph
graphs.FruchtGraph
graphs.FuzzyBallGraph
graphs.GeneralizedPetersenGraph
graphs.GoethalsSeidelGraph
graphs.GoldnerHararyGraph
graphs.GossetGraph
graphs.GrayGraph
graphs.Grid2dGraph
graphs.GridGraph
graphs.GrotzschGraph
graphs.HaemersGraph
graphs.HallJankoGraph
graphs.HanoiTowerGraph
graphs.HararyGraph
graphs.HarborthGraph
graphs.HarriesGraph
graphs.HarriesWongGraph
graphs.HeawoodGraph
graphs.HerschelGraph
graphs.HexahedralGraph
graphs.HigmanSimsGraph
graphs.HoffmanGraph
graphs.HoffmanSingletonGraph
graphs.HoltGraph
graphs.HortonGraph
graphs.HouseGraph
graphs.HouseXGraph
graphs.HyperStarGraph
graphs.IcosahedralGraph
graphs.IntersectionGraph
graphs.IntervalGraph
graphs.IoninKharaghani765Graph
graphs.JankoKharaghaniGraph
graphs.JankoKharaghaniTonchevGraph
graphs.JohnsonGraph
graphs.KingGraph
graphs.KittellGraph
graphs.Klein3RegularGraph
graphs.Klein7RegularGraph
graphs.KneserGraph
graphs.KnightGraph
graphs.KrackhardtKiteGraph
graphs.LCFGraph
graphs.LadderGraph
graphs.LivingstoneGraph
graphs.LjubljanaGraph
graphs.LocalMcLaughlinGraph
graphs.LollipopGraph
graphs.M22Graph
graphs.MarkstroemGraph
graphs.MathonPseudocyclicMergingGraph
graphs.MathonPseudocyclicStronglyRegularGraph
graphs.MathonStronglyRegularGraph
graphs.McGeeGraph
graphs.McLaughlinGraph
graphs.MeredithGraph
graphs.MoebiusKantorGraph
graphs.MoserSpindle
graphs.MuzychukS6Graph
graphs.MycielskiGraph
graphs.MycielskiStep
graphs.NKStarGraph
graphs.NStarGraph
graphs.NauruGraph
graphs.NonisotropicOrthogonalPolarGraph
graphs.NonisotropicUnitaryPolarGraph
graphs.OctahedralGraph
graphs.OddGraph
graphs.OrthogonalArrayBlockGraph
graphs.OrthogonalPolarGraph
graphs.PaleyGraph
graphs.PappusGraph
graphs.PasechnikGraph
graphs.PathGraph
graphs.PerkelGraph
graphs.PermutationGraph
graphs.PetersenGraph
graphs.PoussinGraph
graphs.QueenGraph
graphs.RandomBarabasiAlbert
graphs.RandomBipartite
graphs.RandomBoundedToleranceGraph
graphs.RandomGNM
graphs.RandomGNP
graphs.RandomHolmeKim
graphs.RandomIntervalGraph
graphs.RandomLobster
graphs.RandomNewmanWattsStrogatz
graphs.RandomRegular
graphs.RandomShell
graphs.RandomToleranceGraph
graphs.RandomTree
graphs.RandomTreePowerlaw
graphs.RandomTriangulation
graphs.RingedTree
graphs.RobertsonGraph
graphs.RookGraph
graphs.SchlaefliGraph
graphs.ShrikhandeGraph
graphs.SierpinskiGasketGraph
graphs.SimsGewirtzGraph
graphs.SousselierGraph
graphs.SquaredSkewHadamardMatrixGraph
graphs.StarGraph
graphs.SuzukiGraph
graphs.SwitchedSquaredSkewHadamardMatrixGraph
graphs.SylvesterGraph
graphs.SymplecticDualPolarGraph
graphs.SymplecticGraph
graphs.SymplecticPolarGraph
graphs.SzekeresSnarkGraph
graphs.T2starGeneralizedQuadrangleGraph
graphs.TaylorTwographDescendantSRG
graphs.TaylorTwographSRG
graphs.TetrahedralGraph
graphs.ThomsenGraph
graphs.TietzeGraph
graphs.ToleranceGraph
graphs.Toroidal6RegularGrid2dGraph
graphs.ToroidalGrid2dGraph
graphs.TruncatedIcosidodecahedralGraph
graphs.TruncatedTetrahedralGraph
graphs.TuranGraph
graphs.Tutte12Cage
graphs.TutteCoxeterGraph
graphs.TutteGraph
graphs.UnitaryDualPolarGraph
graphs.UnitaryPolarGraph
graphs.WagnerGraph
graphs.WatkinsSnarkGraph
graphs.WellsGraph
graphs.WheelGraph
graphs.WienerArayaGraph
graphs.WorldMap
graphs.chang_graphs
graphs.cospectral_graphs
graphs.fullerenes
graphs.fusenes
graphs.line_graph_forbidden_subgraphs
graphs.nauty_geng
graphs.petersen_family
graphs.planar_graphs
graphs.quadrangulations
graphs.sage
graphs.strongly_regular_graph
graphs.trees
graphs.triangulations

G.add_cycle
G.add_edge
G.add_edges
G.add_path
G.add_vertex
G.add_vertices
G.adjacency_matrix
G.all_paths
G.allow_loops
G.allow_multiple_edges
G.allows_loops
G.allows_multiple_edges
G.am
G.antisymmetric
G.apex_vertices
G.automorphism_group
G.average_degree
G.average_distance
G.bipartite_color
G.bipartite_sets
G.blocks_and_cut_vertices
G.blocks_and_cuts_tree
G.bounded_outdegree_orientation
G.breadth_first_search
G.bridges
G.canonical_label
G.cartesian_product
G.categorical_product
G.category
G.center
G.centrality_betweenness
G.centrality_closeness
G.centrality_degree
G.characteristic_polynomial
G.charpoly
G.chromatic_number
G.chromatic_polynomial
G.chromatic_quasisymmetric_function
G.chromatic_symmetric_function
G.clear
G.clique_complex
G.clique_maximum
G.clique_number
G.clique_polynomial
G.cliques_containing_vertex
G.cliques_get_clique_bipartite
G.cliques_get_max_clique_graph
G.cliques_maximal
G.cliques_maximum
G.cliques_number_of
G.cliques_vertex_clique_number
G.cluster_transitivity
G.cluster_triangles
G.clustering_average
G.clustering_coeff
G.coarsest_equitable_refinement
G.coloring
G.complement
G.connected_component_containing_vertex
G.connected_components
G.connected_components_number
G.connected_components_sizes
G.connected_components_subgraphs
G.convexity_properties
G.copy
G.cores
G.cycle_basis
G.db
G.degree
G.degree_constrained_subgraph
G.degree_histogram
G.degree_iterator
G.degree_sequence
G.degree_to_cell
G.delete_edge
G.delete_edges
G.delete_multiedge
G.delete_vertex
G.delete_vertices
G.density
G.depth_first_search
G.diameter
G.disjoint_routed_paths
G.disjoint_union
G.disjunctive_product
G.distance
G.distance_all_pairs
G.distance_graph
G.distance_matrix
G.distances_distribution
G.dominating_set
G.dominator_tree
G.dump
G.dumps
G.eccentricity
G.edge_boundary
G.edge_connectivity
G.edge_cut
G.edge_disjoint_paths
G.edge_disjoint_spanning_trees
G.edge_iterator
G.edge_label
G.edge_labels
G.edges
G.edges_incident
G.eigenspaces
G.eigenvectors
G.eulerian_circuit
G.eulerian_orientation
G.export_to_file
G.faces
G.feedback_vertex_set
G.flow
G.fractional_chromatic_index
G.genus
G.get_embedding
G.get_pos
G.get_vertex
G.get_vertices
G.girth
G.gomory_hu_tree
G.graph6_string
G.graphics_array_defaults
G.graphplot
G.graphviz_string
G.graphviz_to_file_named
G.hamiltonian_cycle
G.has_edge
G.has_homomorphism_to
G.has_loops
G.has_multiple_edges
G.has_vertex
G.igraph_graph
G.ihara_zeta_function_inverse
G.incidence_matrix
G.independent_set
G.independent_set_of_representatives
G.is_apex
G.is_arc_transitive
G.is_asteroidal_triple_free
G.is_bipartite
G.is_cartesian_product
G.is_cayley
G.is_chordal
G.is_circulant
G.is_circular_planar
G.is_clique
G.is_connected
G.is_cut_edge
G.is_cut_vertex
G.is_directed
G.is_distance_regular
G.is_drawn_free_of_edge_crossings
G.is_edge_transitive
G.is_equitable
G.is_eulerian
G.is_even_hole_free
G.is_forest
G.is_gallai_tree
G.is_half_transitive
G.is_hamiltonian
G.is_immutable
G.is_independent_set
G.is_interval
G.is_isomorphic
G.is_line_graph
G.is_long_antihole_free
G.is_long_hole_free
G.is_odd_hole_free
G.is_overfull
G.is_partial_cube
G.is_perfect
G.is_planar
G.is_prime
G.is_regular
G.is_semi_symmetric
G.is_split
G.is_strongly_regular
G.is_subgraph
G.is_transitively_reduced
G.is_tree
G.is_triangle_free
G.is_vertex_transitive
G.is_weakly_chordal
G.join
G.kirchhoff_matrix
G.kirchhoff_symanzik_polynomial
G.kronecker_product
G.laplacian_matrix
G.latex_options
G.layout
G.layout_circular
G.layout_default
G.layout_extend_randomly
G.layout_graphviz
G.layout_planar
G.layout_ranked
G.layout_spring
G.layout_tree
G.lex_BFS
G.lexicographic_product
G.line_graph
G.longest_path
G.loop_edges
G.loop_vertices
G.loops
G.lovasz_theta
G.magnitude_function
G.matching
G.matching_polynomial
G.max_cut
G.maximum_average_degree
G.merge_vertices
G.min_spanning_tree
G.minimum_outdegree_orientation
G.minor
G.modular_decomposition
G.multicommodity_flow
G.multiple_edges
G.multiway_cut
G.name
G.neighbor_iterator
G.neighbors
G.networkx_graph
G.num_edges
G.num_faces
G.num_verts
G.number_of_loops
G.odd_girth
G.order
G.orientations
G.parent
G.perfect_matchings
G.periphery
G.plot
G.plot3d
G.radius
G.random_edge
G.random_edge_iterator
G.random_spanning_tree
G.random_subgraph
G.random_vertex
G.random_vertex_iterator
G.rank_decomposition
G.relabel
G.remove_loops
G.remove_multiple_edges
G.rename
G.reset_name
G.save
G.seidel_adjacency_matrix
G.seidel_switching
G.set_edge_label
G.set_embedding
G.set_latex_options
G.set_planar_positions
G.set_pos
G.set_vertex
G.set_vertices
G.shortest_path
G.shortest_path_all_pairs
G.shortest_path_length
G.shortest_path_lengths
G.shortest_paths
G.show
G.show3d
G.size
G.spanning_trees
G.spanning_trees_count
G.sparse6_string
G.spectral_radius
G.spectrum
G.steiner_tree
G.strong_orientation
G.strong_product
G.subdivide_edge
G.subdivide_edges
G.subgraph
G.subgraph_search
G.subgraph_search_count
G.subgraph_search_iterator
G.szeged_index
G.tensor_product
G.to_dictionary
G.to_directed
G.to_partition
G.to_simple
G.to_undirected
G.topological_minor
G.transitive_closure
G.transitive_reduction
G.traveling_salesman_problem
G.treewidth
G.triangles_count
G.tutte_polynomial
G.two_factor_petersen
G.twograph
G.union
G.vertex_boundary
G.vertex_connectivity
G.vertex_cover
G.vertex_cut
G.vertex_disjoint_paths
G.vertex_iterator
G.vertices
G.weighted
G.weighted_adjacency_matrix
G.wiener_index
G.write_to_eps

 

SageMathとグラフ理論(平面グラフ)

問題12.1
(i) 頂点数5の車輪Wheel、 W_{5}が平面グラフであることをグラフで示せ。
(ii) octahedron(八面体)が平面グラフであることをグラフで示せ。

f:id:niming538:20170930094038p:plain

 

すなおに描くと平面グラフになってしまう。

 

問題の意図としては必ずしも平面グラフでないものを平面グラフ的(planar)に描けということなのでしょうが、SageMathは自動的になるべく平面的に描いてしまう。頂点の場所を指定する方法があるだろうけどまだ調べられていません。


# planar01.sage
# attach('planar01.sage')

Gw5=graphs.WheelGraph(5)
p1=plot(Gw5)
Go=graphs.OctahedralGraph()
p2=plot(Go)
# graphics_array([p1,p2])

 

追記: こんなことができました。

 

頂点の配置に、'spring'というのと'circular'というのを指定すると、0を中心に配置するのと、すべての点を円周上に配置するのが選べます。

f:id:niming538:20170930104722p:plain


Gw5.graphplot(save_pos=True, layout='spring')
p3=plot(Gw5)
Gw5.graphplot(save_pos=True, layout='circular')
p4=plot(Gw5)
Go.graphplot(save_pos=True, layout='spring')
p5=plot(Go)
Go.graphplot(save_pos=True, layout='circular')
p6=plot(Go)
graphics_array([p3,p4,p5,p6],2,2)

 

SageMathでグラフ理論(クラトウスキーの定理)

THEOREM 12.2(Kuratowski, 1930). A graph is planar if and only if it contains no subgraph homeomorphic to  K_5 or  K_{3,3}.

 

グラフ Gが平面グラフであるための必要十分条件 G K_5 または K_{3,3}と位相同型な部分グラフを含まないことである。

 

THEOREM 12.3 A graph is planar if and only if it contains no subgraph contractible to  K_5 or  K_{3,3}.

 

contractibleというのは、頂点を重ねること(縮約)によって頂点と辺の数をへらしていくことで、例として、Petersenグラフの内側の5つの点を外側に重ね合わせると次のようになります。

 

# pertsen.sage

G=graphs.PetersenGraph()
p1=plot(G)

G2=copy(G)

G2.merge_vertices([0,5])
G2.merge_vertices([1,6])
G2.merge_vertices([2,7])
G2.merge_vertices([3,8])
G2.merge_vertices([4,9])
p2=plot(G2)
# graphics_array( (p1,p2))

f:id:niming538:20170929154119p:plain