Einführung

In dieser Herausforderung erhalten Sie einen gerichteten Graphen mit Selbstschleifen. Ihre Aufgabe besteht darin, ihn in einen ungerichteten Graphen ohne Selbstschleifen umzuwandeln.

Eingang

Ihre Eingabe ist ein gerichteter Graph, bei dem der Scheitelpunkt {0, 1, ..., n-1}für eine natürliche Zahl festgelegt ist n ≥ 0(oder {1, 2, ..., n}wenn Sie eine 1-basierte Indizierung verwenden). Der Graph wird als längs- gegeben nListe , Lwo Sie L[i]eine Liste der out-Nachbarn von Vertex i. Die Liste [[0,1],[0],[1,0,3],[]]repräsentiert beispielsweise das Diagramm

.-.
| v
'-0<--2-->3
  ^   |
  |   |
  v   |
  1<--'

Beachten Sie, dass die Nachbarlisten nicht unbedingt geordnet sind, aber garantiert keine Duplikate enthalten.

Ausgabe

Ihre Ausgabe ist ein anderes Diagramm im gleichen Format wie die Eingabe, das wie folgt daraus erhalten wird.

1. Löschen Sie alle Self-Loops.
2. Fügen Sie für jede verbleibende Kante u -> vdie umgekehrte Kante hinzu, v -> ufalls diese noch nicht vorhanden ist.

Wie bei der Eingabe sind die Nachbarlisten des Ausgabediagramms möglicherweise ungeordnet, dürfen jedoch keine Duplikate enthalten. Für das obige Diagramm wäre eine korrekte Ausgabe [[1,2],[0,2],[0,1,3],[2]], die das Diagramm darstellt

0<->2<->3
^   ^
|   |
v   |
1<--'

Regeln

In den Diagrammen können Sie 0-basierte oder 1-basierte Indizierung verwenden. Beide Funktionen und vollständige Programme sind akzeptabel. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig.

Testfälle

Diese Testfälle verwenden eine 0-basierte Indizierung. Inkrementieren Sie jede Zahl im 1-basierten Fall. Diese Nachbarlisten werden in aufsteigender Reihenfolge sortiert, sind jedoch nicht erforderlich.

[] -> []
[[0]] -> [[]]
[[],[0,1]] -> [[1],[0]]
[[0,1],[]] -> [[1],[0]]
[[0,1],[0],[1,0,3],[]] -> [[1,2],[0,2],[0,1,3],[2]]
[[3],[],[5],[3],[1,3],[4]] -> [[3],[4],[5],[0,4],[1,3,5],[2,4]]
[[0,1],[6],[],[3],[3],[1],[4,2]] -> [[1],[0,5,6],[6],[4],[3,6],[1],[1,2,4]]
[[6],[0,5,1],[5,4],[3,5],[4],[5,6],[0,3]] -> [[1,6],[0,5],[4,5],[5,6],[2],[1,2,3,6],[0,3,5]]
[[1,0],[5,1],[5],[1],[5,7],[7,1],[],[1]] -> [[1],[0,3,5,7],[5],[1],[5,7],[1,2,4,7],[],[1,4,5]]
[[2,8,0,9],[5,2,3,4],[0,2],[3,7,4],[8,1,2],[5,1,9,2],[6,9],[6,5,2,9,0],[9,1,2,0],[3,9]] -> [[2,7,8,9],[2,3,4,5,8],[0,1,4,5,7,8],[1,4,7,9],[1,2,3,8],[1,2,7,9],[7,9],[0,2,3,5,6,9],[0,1,2,4,9],[0,3,5,6,7,8]]

Pyth, 17 16 Bytes

.e-.|f}k@QTUQbkQ

Probieren Sie es online aus: Demo oder Test Suite

Erläuterung

                   implicit: Q = input
.e             Q   enumerated mapping of Q (k index, b out-neighbors):
     f     UQ         filter [0, 1, ..., len(Q)-1] for elements T, which satisfy:
      }k@QT              k in Q[T]
                      # this are the in-neighbors
   .|        b        setwise union with b 
  -           k       remove k

CJam, 43 40 35 34 33 Bytes

2 Bytes von Sp3000 gespeichert.

Dies begann als eine wirklich elegante Lösung und wurde dann immer schrecklicher, als ich versuchte, einige von mir übersehene Löcher zu flicken. Ich bin mir noch nicht sicher, ob die ursprüngliche Idee noch zu retten ist, aber ich werde mein Bestes geben ...

q~_,,\ff{&W+0=)}_z..-{_,{;(},+}%`

Teste es hier. Alternativ können Sie auch das gesamte Testkabel ausführen .

Ich werde eine Erklärung hinzufügen, sobald ich sicher bin, dass der Patient tot ist.

Python 2, 107 Bytes

Ich versuche immer noch herauszufinden, ob ich mehr Golf spielen kann, aber im Moment ist dies das Beste, was ich tun kann.

def u(g):e=enumerate;o=[set(_)-{i}for i,_ in e(g)];[o[j].add(i)for i,_ in e(o)for j in _];print map(list,o)

Ich benutze Sets, um Duplikate zu vermeiden. Im Gegensatz dazu list.remove(i)wird {S}-{i}auch kein Fehler ausgegeben, wenn inicht vorhanden S.

Ruby, 78 Bytes

Zum Schluss noch etwas Verwendung für die Mengenoperatoren ( [1,2]&[2]==[2]und [3,4,5]-[4]==[3,5]) von Ruby .

->k{n=k.size;n.times{|i|n.times{|j|(k[j]&[i])[0]&&k[i]=(k[i]<<j).uniq-[i]}};k}

ideone , einschließlich aller Testfälle, die es besteht.

CJam, 26 Bytes

l~_,,:T.-_T\ff&Tf.e&.|:e_p

Nicht sehr kurz ...

Erläuterung

l~                           e# Read the input.
  _,,:T                      e# Get the graph size and store in T.
       .-                    e# Remove self-loops from the original input.
         _T\ff&              e# Check if each vertex is in each list, and
                             e# return truthy if yes, or empty list if no.
               Tf.e&         e# Convert truthy to vertex numbers.
                    .|       e# Merge with the original graph.
                      :e_    e# Remove empty lists.
                         p   e# Format and print.

JavaScript (ES6), 96 110

Erstellen von Adjazenzsätzen aus der Adjazenzliste, um Duplikate zu vermeiden. Ad last erstellt die Listen neu, beginnend mit den Sätzen.

//Golfed 
U=l=>
  l.map((m,n)=>m.map(a=>a-n?s[n][a]=s[a][n]=1:0),s=l.map(m=>[]))
  &&s.map(a=>[~~k for(k in a)])

// Ungolfed

undirect=(adList)=>(
  adSets=adList.map(_ => []),
  adList.forEach((curAdList,curNode)=>{
    curAdList.forEach(adNode=>{
      if (adNode!=curNode) {
        adSets[curNode][adNode]=1,
        adSets[adNode][curNode]=1
      }
    })  
  }),
  adSets.map(adSet=>[~~k for(k in adSet)])
)

// Test
out=s=>OUT.innerHTML+=s+'\n'

test=[
 [ [], [] ]
,[ [[0]], [[]] ]
,[ [[],[0,1]] , [[1],[0]] ]
,[ [[0,1],[]] , [[1],[0]] ]

,[ [[0,1],[0],[1,0,3],[]] , [[1,2],[0,2],[0,1,3],[2]] ]
,[ [[3],[],[5],[3],[1,3],[4]] , [[3],[4],[5],[0,4],[1,3,5],[2,4]] ]
,[ [[0,1],[6],[],[3],[3],[1],[4,2]] , [[1],[0,5,6],[6],[4],[3,6],[1],[1,2,4]] ] 
,[ 
   [[6],[0,5,1],[5,4],[3,5],[4],[5,6],[0,3]] ,
   [[1,6],[0,5],[4,5],[5,6],[2],[1,2,3,6],[0,3,5]]  
 ]
,[
  [[1,0],[5,1],[5],[1],[5,7],[7,1],[],[1]] , 
  [[1],[0,3,5,7],[5],[1],[5,7],[1,2,4,7],[],[1,4,5]]
 ]

,[
  [[2,8,0,9],[5,2,3,4],[0,2],[3,7,4],[8,1,2],[5,1,9,2],[6,9],[6,5,2,9,0],[9,1,2,0],[3,9]] ,
  [[2,7,8,9],[2,3,4,5,8],[0,1,4,5,7,8],[1,4,7,9],[1,2,3,8],[1,2,7,9],[7,9],[0,2,3,5,6,9],  [0,1,2,4,9],[0,3,5,6,7,8]]
 ]
] 

show=l=>'['+l.map(a=>'['+a+']').join(',')+']'

test.forEach(t => (
  r = U(t[0]),
  ck = show(r) == show(t[1]),           
  out('Test ' + (ck ? 'OK: ':'FAIL: ') + show(t[0])+' -> ' + 
      '\nResult: ' + show(r) + 
      '\nCheck : ' + show(t[1]) + '\n\n')
) )

<pre id=OUT></pre>

Java, 150

a->{int i=0,j,k=a.size();for(;i<k;a.get(i).remove((Object)i++))for(j=k;j-->0;)if(a.get(j).contains(i)&!a.get(i).contains(j))a.get(i).add(j);return a;}

Erweiterter, lauffähiger Code:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.Function
public class C {
    static Function<List<List<Integer>>, List<List<Integer>>> f = a -> {
        int i = 0, j, k = a.size();
        for (; i < k; a.get(i).remove((Object) i++)) {
            for (j = k; j-- > 0;) {
                if (a.get(j).contains(i) & !a.get(i).contains(j)) {
                    a.get(i).add(j);
                }
            }
        }
        return a;
    };
    public static void main(String[] args) {
        System.out.println(f.apply(new ArrayList(Arrays.asList(
                new ArrayList(Arrays.asList(0, 1)),
                new ArrayList(Arrays.asList(1)),
                new ArrayList(Arrays.asList(1, 0, 3)),
                new ArrayList(Arrays.asList()))
        )));
    }
}

Groovy - 87

u={g->g.eachWithIndex{n,i->g[i]=n-i;g[i].each{g[it]<<i}};g.each{it=it.sort().unique()}}

Vollständiges Skript zum Ausführen von Tests:

u={g->g.eachWithIndex{n,i->g[i]=n-i;g[i].each{g[it]<<i}};g.each{it=it.sort().unique()}}
assert u([]) == []
assert u([[0]]) == [[]]
assert u([[],[0,1]]) == [[1],[0]]
assert u([[0,1],[]]) == [[1],[0]]
assert u([[0,1],[0],[1,0,3],[]]) == [[1,2],[0,2],[0,1,3],[2]]
assert u([[3],[],[5],[3],[1,3],[4]]) == [[3],[4],[5],[0,4],[1,3,5],[2,4]]
assert u([[0,1],[6],[],[3],[3],[1],[4,2]]) == [[1],[0,5,6],[6],[4],[3,6],[1],[1,2,4]]
assert u([[6],[0,5,1],[5,4],[3,5],[4],[5,6],[0,3]]) == [[1,6],[0,5],[4,5],[5,6],[2],[1,2,3,6],[0,3,5]]
assert u([[1,0],[5,1],[5],[1],[5,7],[7,1],[],[1]]) == [[1],[0,3,5,7],[5],[1],[5,7],[1,2,4,7],[],[1,4,5]]
assert u([[2,8,0,9],[5,2,3,4],[0,2],[3,7,4],[8,1,2],[5,1,9,2],[6,9],[6,5,2,9,0],[9,1,2,0],[3,9]]) == [[2,7,8,9],[2,3,4,5,8],[0,1,4,5,7,8],[1,4,7,9],[1,2,3,8],[1,2,7,9],[7,9],[0,2,3,5,6,9],[0,1,2,4,9],[0,3,5,6,7,8]]

Mathematica, 84 66 64 Bytes

1-basierte Indizierung verwenden.

MapIndexed[Union[#,First/@l~Position~Tr@#2]~Complement~#2&,l=#]&

Python 3, 127 Bytes

l=list;g=l(map(set,eval(input())))
for i in range(len(g)):
    for j in g[i]:g[j]=g[j]^g[j]&{j}|{i}
print(l(map(l,g)))

Versuchen Sie es online

Nicht mein bester Versuch ...