ILP Part 46 — Gray Code – Random IT Utensils

This is the forty sixth part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Hi. Today we are going to generate Gray code using ILP. I am not going to cover theory here, you can find it on Wikipedia.

We want to generate $N$ codes where $N$ is power of two. First, we define $N$ non-negative integer variables. Next, we add constraints that make all variables different. Finally, we need to make sure that variables represent Gray codes.

For each pair of variables we first calculate their unsigned magnitude representation, next we xor digits at the same positions from both of the representations. Next, we sum xors and add constraint that this sum must be equal to one.

The code solves the problem:

using CplexMilpManager.Implementation;
using MilpManager.Abstraction;
using MilpManager.Implementation;
using System;
using System.Linq;

namespace GrayCodes
{
    class Program
    {
        private const int N = 32;

        static void Main(string[] args)
        {
            var solver = new CplexMilpSolver(10);

            var variables = Enumerable
                .Range(0, N)
                .Select(v => solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set(ConstraintType.LessOrEqual, solver.FromConstant(N - 1)))
                .ToArray();

            var binaryDigits = variables
                .Select(v => v.CompositeOperation(CompositeOperationType.UnsignedMagnitudeDecomposition).ToArray())
                .ToArray();

            for(int index = 0; index < N; ++index)
            {
                int otherIndex = (index + 1) % N;

                solver.Operation(OperationType.Addition, 
                    Enumerable
                        .Range(0, solver.IntegerWidth)
                        .Select(i => solver.Operation(OperationType.ExclusiveDisjunction, binaryDigits[index][i], binaryDigits[otherIndex][i]))
                        .ToArray()
                    )
                    .Set(ConstraintType.Equal, solver.FromConstant(1));
            }

            solver.Set(CompositeConstraintType.AllDifferent, variables.First(), variables.Skip(1).ToArray());

            solver.AddGoal("GOAL", solver.FromConstant(0));

            solver.Solve();

            foreach (var v in variables)
            {
                Console.WriteLine((int)v.GetValue());
            }
        }
    }
}

using CplexMilpManager.Implementation;

using MilpManager.Abstraction;

using MilpManager.Implementation;

using System;

using System.Linq;

namespace GrayCodes

{

class Program

{

private const int N = 32;

static void Main(string[] args)

{

var solver = new CplexMilpSolver(10);

var variables = Enumerable

.Range(0, N)

.Select(v => solver.CreateAnonymous(Domain.PositiveOrZeroInteger).Set(ConstraintType.LessOrEqual, solver.FromConstant(N - 1)))

.ToArray();

var binaryDigits = variables

.Select(v => v.CompositeOperation(CompositeOperationType.UnsignedMagnitudeDecomposition).ToArray())

.ToArray();

for(int index = 0; index < N; ++index)

{

int otherIndex = (index + 1) % N;

solver.Operation(OperationType.Addition,

Enumerable

.Range(0, solver.IntegerWidth)

.Select(i => solver.Operation(OperationType.ExclusiveDisjunction, binaryDigits[index][i], binaryDigits[otherIndex][i]))

.ToArray()

)

.Set(ConstraintType.Equal, solver.FromConstant(1));

}

solver.Set(CompositeConstraintType.AllDifferent, variables.First(), variables.Skip(1).ToArray());

solver.AddGoal("GOAL", solver.FromConstant(0));

solver.Solve();

foreach (var v in variables)

{

Console.WriteLine((int)v.GetValue());

}