How to correctly enumerate all the schemes of this hexahedral coloring problem?

Choose several colors from the given six different colors to dye six faces of a cube, and dye each two faces with common edges into different colors. How many different dyeing schemes are there?

Note: if we dye two identical cubes, we can make the six corresponding faces of the two cubes dyed the same by proper flipping, then we say that the two cubes have the same dyeing scheme.

Show[Graphics3D[   Rotate[Cuboid[{0, 0, 0}, {1, 2, 1}], 0 Degree, {0, 0, 1}],    Axes -> True], i = 1;   Graphics3D[   Table[Text[Style[ToString[i++], 15], {x, y, z}], {x, 0, 1}, {y, 0,      2, 2}, {z, 0, 1}]]] 

enter image description here

g0 = Graph[(Sort /@        Flatten[Map[Thread[#[[1]] \[UndirectedEdge] #[[2]]] &,         {{1, {2, 3, 5}},          {2, {1, 4, 6}},          {3, {1, 4, 7}},          {4, {2, 3, 8}},          {5, {1, 6, 7}},          {6, {2, 5, 8}},          {7, {3, 5, 8}},          {8, {4, 6, 7}}}]]) // DeleteDuplicates,     VertexLabels -> "Name"]; ChromaticPolynomial[g0, 6]  poly = CycleIndexPolynomial[DihedralGroup[8],    Array[Subscript[a, ##] &, 6]] 

The result of the above code is 198030, but the reference answer is 230. How to correctly list all the solutions to this problem?

Enumerate all valid orders of subset sums

Given an positive integer $ n$ , we define an order of subset sums to be a sequence of all subsets of $ \{1,\ldots,n\}$ . For example, when $ n=2$ , the sequence $ \emptyset,\{1\},\{2\},\{1,2\}$ is an order of subset sums.

We call an order of subset sums $ S_1,\ldots,S_{2^n}$ valid if there exist real numbers $ 0<x_1<\cdots<x_n$ such that $ \sum_{i\in S_1}x_i<\cdots<\sum_{i\in S_{2^n}}x_i$ . For example, when $ n=2$ , the sequence $ \emptyset,\{1\},\{2\},\{1,2\}$ is a valid order of subset sums, but the sequence $ \emptyset,\{1\},\{1,2\},\{1\}$ is not a valid order of subset sums because we cannot make $ x_1+x_2<x_1$ .

The question is, given $ n$ , how to enumerate all possible valid orders of subset sums. I know this problem cannot be solved in time polynomial in $ n$ , because there may be exponentially many valid orders of subset sums, so an algorithm with exponential time is welcome.

A trivial algorithm would be to iterate over all possible orders of subset sums, and check for each one if it is valid. But I cannot even find an (efficient) way to check if an order of subset sums is valid.

Enumerate all paths in a given series-parallel graph

Series parallel graph is well-known and widely used. It has a single source and a single destination. The graph can be formed by means of recursive serial or parallel composition.

SP-Graph

I have a graph dataset that is of this type, and I have to enumerate all paths in the series-parallel graphs. Are there any existed algorithms? If so, what is the time complexity of it?

Enumerate all members and types with specific attributes

I have a use-case where I need to retrieve all members with specific attributes in the class and interface hierarchy – I usually need the first match and apply its rules to child members. The built-in GetCustomAttributes are too limited becuase they work only for a single member and don’t support interfaces.


Implementation

To solve this I wrote my own extension that returns a collection of AttributeCollection<T> instances. Each one contains the member the attributes are applied to and the matched attributes.

There are couple of rules that this needs to follow in order for the results to be useful because attribute settings are then propagated to child members:

  • properties come before types
  • classes come before interfaces
  • skip duplicate results
public static class Extensions {     public static IEnumerable<AttributeCollection<T>> EnumerateCustomAttributes<T>(this MemberInfo member) where T : Attribute     {         if (member == null) throw new ArgumentNullException(nameof(member));          var queue = new Queue<MemberInfo>         {             member,         };          // Helps to suppress duplicate results when same member is seen multiple times.         var seenAttributeCollections = new HashSet<AttributeCollection<T>>();          while (queue.Any())         {             var current = queue.Dequeue();              if (current.GetCustomAttributes<T>() is var attributes && attributes.Any())             {                 var attributeCollection = new AttributeCollection<T>(current, attributes);                 if (seenAttributeCollections.Add(attributeCollection))                 {                     yield return attributeCollection;                 }             }              if (current is PropertyInfo property)             {                 queue.Enqueue(property.DeclaringType);             }              if (current is Type type)             {                 // The order matters so enqueue properties before their declaring types and base classes before interfaces.                  if (type.IsSubclass())                 {                     if (type.BaseType.GetProperty(member.Name) is PropertyInfo otherProperty)                     {                         queue.Enqueue(otherProperty);                     }                      queue.Enqueue(type.BaseType);                 }                  foreach (var interfaceType in type.GetInterfaces())                 {                     if (interfaceType.GetProperty(member.Name) is PropertyInfo otherProperty)                     {                         queue.Enqueue(otherProperty);                     }                      queue.Enqueue(interfaceType);                 }             }         }     }      public static bool IsSubclass(this Type type)     {         return type.IsClass && type.BaseType != typeof(object);     }    } 

This class helps handling equality and results:

public class AttributeCollection<T> : List<T>, IEquatable<AttributeCollection<T>> where T : Attribute {     private static readonly IEqualityComparer<AttributeCollection<T>> Comparer = EqualityComparerFactory<AttributeCollection<T>>.Create     (         // When either one is True then we consider both collections equal.         equals: (x, y) => (x.Member == y.Member) || x.SequenceEqual(y)     );      public AttributeCollection(MemberInfo member, IEnumerable<T> attributes) : base(attributes)     {         Member = member;     }      public MemberInfo Member { get; }      public bool Equals(AttributeCollection<T> other) => Comparer.Equals(this, other);      public override bool Equals(object obj) => obj is AttributeCollection<T> ac && Equals(ac);      public override int GetHashCode() => 0; // Always use 'equals'. } 

Demo

I used this code to test that extension:

void Main() {     typeof(T3).GetProperty(nameof(T3.P1)).EnumerateCustomAttributes<A0>().Dump(); // <-- 6 results     typeof(T3).GetProperty(nameof(T3.P1)).EnumerateCustomAttributes<A1>().Dump(); // <-- 5 results     typeof(T3).GetProperty(nameof(T3.P1)).EnumerateCustomAttributes<A2>().Dump(); // <-- 3 results }  [A1(V = "I1")] interface I1 {     [A1(V = "I1.P1")]     string P1 { get; set; } }  [A2(V = "T1")] class T1 : I1 {     [A1(V = "T1.P1")]     public virtual string P1 { get; set; } }  class T2 : T1 { }  [A1(V = "T3"), A2(V = "T3")] class T3 : T2 {     [A1(V = "T3.P1"), A2(V = "T3.P1")]     public override string P1 { get; set; } }  interface IA {     string V { get; set; } } [AttributeUsage(AttributeTargets.All, AllowMultiple = true)] abstract class A0 : Attribute, IA { public abstract string V { get; set; } } class A1 : A0 { public override string V { get; set; } } class A2 : A0 { public override string V { get; set; } } 

In this example you’ll notice that I use both an interface and an abstract class overriding the V property. It turned out that I cannot use a single property on the base class because the Attribute.Equals method won’t see it and will not recognize two different attributes correctly. See this question.


If you’re going to try this demo in LINQPad then you’ll need this header as I’m using some of my helpers here:

<Query Kind="Program">   <NuGetReference>Reusable.Core</NuGetReference>   <Namespace>Reusable.Extensions</Namespace>   <Namespace>Reusable.Collections</Namespace> </Query> 

Real-world example

I’ll be using it for retrieving UseX attributes in a model like this one:

[UsePrefix("app"), UseNamespace, UseType, UseMember] [TrimStart("I")] public interface IDemo : INamespace {     [UseType, UseMember]     object Greeting { get; } // <-- will use its own attributes      [Tag("io")]     object ReadFile { get; } // <-- will use type's attributes } 

Questions

So, what do you think about this implementation? Am I missing anything important here? Is there anything you would improve?

Enumerate over all halting Turing Machines?

I understand that it is possible to enumerate over all Turing Machines. My understanding of how this works is by fixing an encoding of natural numbers to TM descriptions, and then enumerating the natural numbers and checking whether each number describes a syntactically well-defined TM.

I am wondering how it is possible to enumerate over all halting TMs. My intuition tells me that since the halting problem is undecidable, it should not be possible to filter an enumeration of all TM descriptions to only those TM descriptions which describe halting TMs.

Nevertheless, I recently came across a well-reputed paper that used an enumeration of all halting Turing Machines (see Proposition 1, pg. 2). I’d appreciate any help in understanding this.

Can we enumerate finite sequences which have no halting continuation?

Note: this question has been cross-posted to Math.SE, after about a week here.

I am trying to deepen my understanding of the relationship between the Halting Problem and Godel’s Completeness Theorem (not Incompleteness).

Specifically, as I understand it the Completeness Theorem guarantees a finite proof for any first-order logical statement which holds in all countable models of a first-order theory. (This is my restatement of Wikipedia’s “Every syntactically consistent, countable first-order theory has a finite or countable model.”)

Since the statement “Program $ P_n$ (encoded by integer $ n$ ) does not halt” can presumably be stated in first-order logic and cannot in general be proven, we need to understand why (for given $ n$ ) it does not hold in all countable models.

Intuitively, I expect that any countable model can be encoded as an infinite program for a Turing machine, eg by listing the countable set of first-order propositions. Likewise, I expect that any such “infinite Turing machine” can be identified with a countable first-order theory, by the Church-Turing thesis plus induction.

So, just as the Completeness Theorem fails to “solve” arithmetic because of non-standard models with infinite integers (which eg satisfy otherwise unsatisfiable Diophantine equations), I’m speculating that it fails for Turing machines because of non-standard models with “infinite programs”.

But by my understanding statements which are true in all models (including non-standard / infinite ones) should still be provable. So I expect that if some finite set of axioms, which “pins down” some finite set of digits of a potentially infinite program, is enough to prevent the possibility of halting, we should be able to prove it.

Or in other words, if a finite sequence does not have any continuation which encodes a halting program, that should be provable.

Does my logic hold? Or what am I misunderstanding?

The reason this is not trivially wrong by Rice’s Theorem is that it’s a property of the program itself, rather than the language recognized by that program, which is $ \emptyset$ for the programs I’m talking about.