Ich habe ein Kombinatorik-Problem , das ich auf den OEIS anwenden möchte - das Problem ist, dass ich nicht genug Begriffe habe. Diese Code-Abfrage soll mir helfen, mehr Begriffe zu berechnen. Der Gewinner ist der Benutzer mit dem Beitrag, der die meisten Begriffe enthält.

Das Problem

Angenommen, ich gebe Ihnen eine dreieckige Anordnung von Glühbirnen mit der Seitenlänge $n$ :

     o
    o o
   o o o
  o o o o
 o o o o o
o o o o o o
1 2  ...  n

Ich werde drei Glühbirnen einschalten, die wie im folgenden Beispiel ein "aufrechtes" gleichseitiges Dreieck bilden:

     o
    o x
   o o o
  o o o o
 o x o o x
o o o o o o

Bevor ich das Licht einschalte, müssen Sie so viele Glühbirnen wie möglich aus dem Array entfernen, ohne die Fähigkeit zu verlieren, das eingeschaltete Dreieck der Glühbirnen abzuleiten. Um klar zu sein, wenn eine Glühbirne entfernt wurde, leuchtet sie nicht, wenn ihre Position eingeschaltet ist.

Wenn Sie zum Beispiel die folgenden (mit gekennzeichneten .) Lampen entfernen, werden nur die folgenden zwei Leuchten eingeschaltet (mit gekennzeichnet x), was ausreicht, um die dritte (nicht beleuchtete) Position eindeutig zu bestimmen:

     .              .
    . o            . x
   . . o          . . o
  o o o .   =>   o o o .
 o o o o .      o x o o . <- the third unlit position
o . . . o o    o . . . o o

Es a(n)sei die maximale Anzahl von Lampen, die entfernt werden können, ohne dass Unklarheiten auftreten.

Beispiel

Mit einem naiven Algorithmus habe ich Werte bis zu einem Dreieck mit der Seitenlänge 7 überprüft, wie unten gezeigt:

                                                                      .
                                                      .              . o
                                        .            . o            o . o
                           .           . .          . . o          . o o .
              .           . .         . o o        o o o .        o o . o .
 .           . .         . o o       o o . o      o o o o .      o . o . o o
. .         . o o       . o o o     o . . o o    o . . . o o    o . o . o o o

a(2) = 3    a(3) = 4    a(4) = 5    a(5) = 7     a(6) = 9       a(7) = 11

Wertung

Die Übermittlung, die die Sequenz [a(2), a(3), ..., a(n)]für die größten n berechnet, gewinnt. Wenn zwei Einreichungen identische Sequenzen aufweisen, gewinnt die zuvor veröffentlichte.

Obwohl dies für die Einreichung nicht erforderlich ist, wäre es für mich aufschlussreich, wenn Sie eine Konstruktion der resultierenden Triangluar-Arrays wie im obigen Beispiel posten.

Python 3 ,n=8

import itertools
from ortools.sat.python import cp_model


def solve(n):
    model = cp_model.CpModel()
    solver = cp_model.CpSolver()
    cells = {
        (y, x): model.NewBoolVar(str((y, x)))
        for y in range(n) for x in range(y + 1)}
    triangles = [
            {cells[v] for v in ((y1, x1), (y2, x1), (y2, x1 + y2 - y1))}
            for (y1, x1) in cells.keys() for y2 in range(y1 + 1, n)]
    for t1, t2 in itertools.combinations(triangles, 2):
        model.AddBoolOr(t1.symmetric_difference(t2))
    model.Minimize(sum(cells.values()))
    solver.Solve(model)
    return len(cells) - round(solver.ObjectiveValue())


for n in itertools.count(2):
    print('a(%d) = %d' % (n, solve(n)))

Verwendet den CP-SAT-Solver von Google OR-Tools .

Nach einer Laufzeit von ca. 30 Sekunden wird Folgendes ausgegeben:

a(2) = 3
a(3) = 4
a(4) = 5
a(5) = 7
a(6) = 9
a(7) = 11
a(8) = 13

n=9$n^6$a(9)=15n=8

Wie es funktioniert

$T_1$$T_2$$T_1$$T_2$

Daher kann die Frage als SAT-Problem mit einer Einschränkung für jedes Dreieckspaar umformuliert werden.

PS: Ich würde sehr gerne ein Beispiel für n=8hinzufügen, aber ich habe Probleme mit dem SAT-Solver, der die Lösungen anscheinend für sich behalten möchte.

Beziehen der Lösungen aus dem Programm von @ Delfad0r

Ich habe das Programm von @ Delfad0r auf Ausgabelösungen erweitert. Es gibt auch Zwischenergebnisse, so dass Sie die Ausgabe wie folgt erhalten:

Solving n = 8:
a(8) >= 9
a(8) >= 10
a(8) >= 11
a(8) >= 12
a(8) >= 13
       o
      . o
     . o o
    . o o .
   o o . o o
  o o o o . .
 o . . o o o .
o . . o . o o o
a(8) = 13

Solving n = 9:
a(9) >= 10
a(9) >= 13
a(9) >= 14
a(9) >= 15
        o
       o o
      o . .
     o . o o
    . o . o o
   . o o o o o
  o o o . o . .
 o o o . . . o o
. o o o o o o . .
a(9) = 15

Diese Berechnung dauerte mehrere Stunden.

Wenn Sie ungeduldig werden und drücken, Ctrl-Cnachdem eine möglicherweise nicht optimale Lösung gefunden wurde, zeigt das Programm diese Lösung an. Das dauert also nicht lange:

                   .
                  o o
                 . o o
                . o o o
               o o . o o
              o . o o o .
             o . o . o o o
            . o o o o o . o
           o . . o o o o o o
          o o o o o o o o o .
         o o . o o o o . o o o
        o o o o o o . o . o o o
       o . o o . o o o o o o o o
      o o o . o o o o o . o o o o
     o o o . o o o o o o o o . . o
    o o o o o o o o o o o . o . . o
   o o o o . o o o o . o o o o o . o
  o o o o o o o o . o o . . o o o o .
 o o o o . o o . o . o o o o o o . o o
o o . o o . o o o o . o o o . o o o o o
a(20) >= 42

Hier ist das erweiterte Programm:

import itertools
from ortools.sat.python import cp_model

class ReportPrinter(cp_model.CpSolverSolutionCallback):

    def __init__(self, n, total):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__n = n
        self.__total = total

    def on_solution_callback(self):
        print('a(%d) >= %d' %
              (self.__n, self.__total-self.ObjectiveValue()) )

def solve(n):
    model = cp_model.CpModel()
    solver = cp_model.CpSolver()
    cells = {
        (y, x): model.NewBoolVar(str((y, x)))
        for y in range(n) for x in range(y + 1)}
    triangles = [
            {cells[v] for v in ((y1, x1), (y2, x1), (y2, x1 + y2 - y1))}
            for (y1, x1) in cells.keys() for y2 in range(y1 + 1, n)]
    for t1, t2 in itertools.combinations(triangles, 2):
        model.AddBoolOr(t1.symmetric_difference(t2))
    model.Minimize(sum(cells.values()))
    print('Solving n = %d:' % n)
    status = solver.SolveWithSolutionCallback(model, ReportPrinter(n,len(cells)))
    if status == cp_model.OPTIMAL:
        rel = '='
    elif status == cp_model.FEASIBLE:
        rel = '>='
    else:
        print('No result for a(%d)\n' % n)
        return
    for y in range(n):
        print(' '*(n-y-1), end='')
        for x in range(y+1):
            print('.o'[solver.Value(cells[(y,x)])],end=' ')
        print()
    print('a(%d) %s %d' % (n, rel, len(cells) - solver.ObjectiveValue()))
    print()

for n in itertools.count(2):
    solve(n)

Python 3

Basierend auf der Antwort von Delfad0r folgt dieser Vorgang meist demselben logischen Ablauf, indem Dreieckspaare überprüft und die Konfiguration validiert werden, wenn keine Dreieckspaare vorhanden sind, die diese Validierung nicht bestehen. Da ich außer itertools und copy keine Bibliotheken verwendet habe, habe ich die volle Kontrolle über das Speichern der Beispiele, die im gesamten Programm vorkommen.

examples = dict() # stores examples by key pair of n to a tuple with the triangle and number of lights turned off

for n in range(3, 8):
    tri = [] # model of the triangle, to be filled with booleans representing lights
    tri_points = [] # list of tuples representing points of the triangle
    for i in range(n):
        tri.append([True]*(i + 1))
        for j in range(i+1):
            tri_points.append((i, j))

    t_set = [] # list of all possible triangles from tri, represented by lists of points
    for i in range(n):
        for j in range(len(tri[i])):
            for k in range(1, n - i):
                t_set.append([(i, j), (i + k, j), (i + k, j + k)])

    from itertools import combinations
    import copy

    # validates whether or not a triangle of n lights can have i lights turned off, and saves an example to examples if validated
    def tri_validate(x):
        candidate_list = list(combinations(tri_points, x))
        tri_pairs = list(combinations(t_set, 2))
        for candidate in candidate_list:
            temp_tri = copy.deepcopy(tri)
            valid = False
            for point in candidate:
                (row, col) = point
                temp_tri[row][col] = False
            for pair in tri_pairs:
                valid = False
                (tri1, tri2) = pair
                for point in tri1:
                    if not valid:
                        if point not in tri2:
                            (row, col) = point
                            if temp_tri[row][col]:
                                valid = True
                for point in tri2:
                    if not valid:
                        if point not in tri1:
                            (row, col) = point
                            if temp_tri[row][col]:
                                valid = True
                if not valid:
                    break
            if valid:
                examples[n] = (temp_tri, x)
                return True
        return False

    # iterates up to the point that validation fails, then moves on to the next n
    for i in range(len(tri_points)):
        if tri_validate(i + 1):
            continue
        break

Das Problem ist, dass es nicht sehr effizient ist. Es läuft bis zu n=5diesem Punkt sehr schnell , verlangsamt sich jedoch ab diesem Punkt erheblich. Bei n=6dauert es eine Minute , um herumlaufen, und es ist viel langsamer an n=7. Ich stelle mir vor, dass mit diesem Programm viele Effizienzverbesserungen vorgenommen werden können, aber es handelt sich um einen schnell erstellten Entwurf einer guten Lösung mit viel mehr Flexibilität, um das Innenleben dieser Methode zu überprüfen. Ich werde im Laufe der Zeit schrittweise daran arbeiten.