Smallest set of generators

[thchr]

It would be cool, in principle, to be able to return a set of generators that have minimal cardinality (i.e., include fewest possible elements) - often, that gives the clearest physical picture of what the group really "contains".
Note that this is not what generators return generally. Instead, it follows ITA/Bilbao's data and conventions which focus on making generators of distinct space groups with similar crystal systems as similar as possible (even at the cost of including additional, even redundant, generators).

Two things to consider:

• Bikeshedding an interface to get this. Maybe something like generators(...; minimal=true) (although minimal is a bit tricky as a keyword since it actually has a subtly different meaning than "smallest-size" set in the context of groups).

• Actually computing a representative of the smallest-size generators in a provable fashion. In general, trying this in a naive way runs into problems with exponential scaling in the number of group elements. E.g., this naive implementation usually just cannot deal when group elements go beyond ~16:

  using Crystalline
  
  function form_all_minor_subsets(v::AbstractVector)
      vs′ = [Vector{eltype(v)}(undef, length(v)-1) for _ in 1:length(v)]
      for (i,v′) in enumerate(vs′)
          v′[1:i-1] .= v[1:i-1]
          v′[i:end] .= v[i+1:end]
      end
      return vs′
  end
  
  function find_smallest_subset_generator(orig_gens::AbstractVector, N)
      subset_gens = form_all_minor_subsets(orig_gens)
  
      q = Vector{eltype(orig_gens)}[]
      for gens in subset_gens
          new_group = generate(gens)
          if length(new_group) == N
              smaller_subset_gens = find_smallest_subset_generator(gens, N)
              if smaller_subset_gens === nothing
                  push!(q, gens)
              else
                  append!(q, smaller_subset_gens)
              end
          end
      end
      if isempty(q)
          return nothing
      else
          min_gens_length = minimum(length.(q))
          return unique!(q[findall(v ->  length(v)==min_gens_length, q)])
      end
  end
  find_smallest_subset_generator(orig_gens::AbstractVector) = find_smallest_subset_generator(orig_gens, length(orig_gens))

[thchr]

An implementation with much better scaling is to start from the "bottom" instead, starting from small generator sizes rather than big: i.e., checking from small orders whether it is possible to generate the group by any possible subset of length n of the group; if not, increment n and start again:

using Combinatorics # for `combinations`

function minimal_generators(g; cntr::Union{Nothing, Char}=nothing)
    N = length(g)
    N == 1 && return g[1:1]

    idx_one = findfirst(isone, g)
    isnothing(idx_one) && error("group must contain identity element")
    opidxs = deleteat!(collect(1:N), idx_one) # exclude identity from candidacy as generator
    for n in 1:div(N, 2)
        for idxs in combinations(opidxs, n)
            gens = g[idxs]
            g′ = generate(gens; cntr)
            length(g′) == N && return gens # return first set of minimal generators found
        end
    end
    error("failed to find a set of generators; provided operations may not form a group")
end
minimal_generators(lg::LittleGroup; cntr=centering(lg), kws...) = minimal_generators(operations(lg); cntr, kws...)

This finishes in about ~30 seconds when run over all space groups (with ~75% of that time spent for space group 229):

julia> sgs = spacegroup.(1:230)
julia> @time minimal_generators.(sgs)
 31.712116 seconds (1.60 M allocations: 1.407 GiB, 0.48% gc time, 0.11% compilation time)

The maximum "minimal" generator order is 5.

If we only input groups in primitive settings, this runs even faster:

julia> @time minimal_generators.(primitivize.(sgs))
 0.304367 seconds (151.99 k allocations: 73.213 MiB, 2.29% gc time)

So that's a potential optimization (but in this case, the centering translations would have to act as auxiliary generators - so the overall number of generators is actually bigger).

[thchr]

This currently has an implementation in KdotP.jl (https://github.com/thchr/KdotP.jl/blob/master/src/generator_indices.jl) that should be moved to Crystalline.jl:

https://github.com/thchr/KdotP.jl/blob/0c38990c9ee63474c9b52e64458711657c12434f/src/generator_indices.jl#L6C1-L32C4