Given a list of words, determine whether the words can be chained to form a circle

Question

Given a list of words, determine whether the words can be chained to form a circle. A word X can be placed in front of another word Y in a circle if the last character of X is the same as the first character of Y. For example, the words ['chair', 'height', 'racket', touch', 'tunic'] can form the following circle: chair --> racket --> touch --> height --> tunic --> chair The output it has to be a txt file with one word per line, ex: chair racket touch height tunic

I searched for the solution, but i only managed to get the partial solution which answers wether or not it can be a circle.

# Python program to check if a given directed graph is Eulerian or not
CHARS = 26

# A class that represents an undirected graph
class Graph(object):
    def __init__(self, V):
        self.V = V   # No. of vertices
        self.adj = [[] for x in range(V)] # a dynamic array
        self.inp = [0] * V

    # function to add an edge to graph
    def addEdge(self, v, w):
        self.adj[v].append(w)
        self.inp[w]+=1

    # Method to check if this graph is Eulerian or not
    def isSC(self):
        # Mark all the vertices as not visited (For first DFS)
        visited = [False] * self.V

        # Find the first vertex with non-zero degree
        n = 0
        for n in range(self.V):
            if len(self.adj[n]) > 0:
                break

        # Do DFS traversal starting from first non zero degree vertex.
        self.DFSUtil(n, visited)

        # If DFS traversal doesn't visit all vertices, then return false.
        for i in range(self.V):
            if len(self.adj[i]) > 0 and visited[i] == False:
                return False

        # Create a reversed graph
        gr = self.getTranspose()

        # Mark all the vertices as not visited (For second DFS)
        for i in range(self.V):
            visited[i] = False

        # Do DFS for reversed graph starting from first vertex.
        # Starting Vertex must be same starting point of first DFS
        gr.DFSUtil(n, visited)

        # If all vertices are not visited in second DFS, then
        # return false
        for i in range(self.V):
            if len(self.adj[i]) > 0 and visited[i] == False:
                return False

        return True

    # This function returns true if the directed graph has an eulerian
    # cycle, otherwise returns false
    def isEulerianCycle(self):

        # Check if all non-zero degree vertices are connected
        if self.isSC() == False:
            return False

        # Check if in degree and out degree of every vertex is same
        for i in range(self.V):
            if len(self.adj[i]) != self.inp[i]:
                return False

        return True

    # A recursive function to do DFS starting from v
    def DFSUtil(self, v, visited):

        # Mark the current node as visited and print it
        visited[v] = True

        # Recur for all the vertices adjacent to this vertex
        for i in range(len(self.adj[v])):
            if not visited[self.adj[v][i]]:
                self.DFSUtil(self.adj[v][i], visited)

    # Function that returns reverse (or transpose) of this graph
    # This function is needed in isSC()
    def getTranspose(self):
        g = Graph(self.V)
        for v in range(self.V):
            # Recur for all the vertices adjacent to this vertex
            for i in range(len(self.adj[v])):
                g.adj[self.adj[v][i]].append(v)
                g.inp[v]+=1
        return g

# This function takes an of strings and returns true
# if the given array of strings can be chained to
# form cycle
def canBeChained(arr, n):

    # Create a graph with 'alpha' edges
    g = Graph(CHARS)

    # Create an edge from first character to last character
    # of every string
    for i in range(n):
        s = arr[i]
        g.addEdge(ord(s[0])-ord('a'), ord(s[len(s)-1])-ord('a'))

    # The given array of strings can be chained if there
    # is an eulerian cycle in the created graph
    return g.isEulerianCycle()

# Driver program
arr1 = ["for", "geek", "rig", "kaf"]
n1 = len(arr1)
if canBeChained(arr1, n1):
    print ("Can be chained")
else:
    print ("Cant be chained")

arr2 = ["aab", "abb"]
n2 = len(arr2)
if canBeChained(arr2, n2):
    print ("Can be chained")
else:
    print ("Can't be chained")

Source: https://www.geeksforgeeks.org/given-array-strings-find-strings-can-chained-form-circle/

This solution only returns the Boolean statement of the list, it means that if there is a circle it will output True. The goal for me is to try and expand this solution to give the list separated, i will give another example:

Input:
{"for", "geek", "rig", "kaf"}

Output:
for
rig
geek
kaf
for

Answer 1

The problem you're describing is the Eulerian circuit problem.

There is an algorithm implemented in module networkx:

• networkx.algorithms.euler.eulerian_circuit

from networkx import DiGraph, eulerian_circuit

words = ['chair', 'height', 'racket', 'touch', 'tunic']
G = DiGraph()
G.add_weighted_edges_from(((w[0], w[-1], w) for w in words), weight='word')
result = [G[a][b]['word'] for a,b in eulerian_circuit(G)]

print(result)
# ['chair', 'racket', 'touch', 'height', 'tunic']

Answer 2

This seems like a lot of effort to solve this problem. Consider a simple solution like:

from collections import defaultdict

words = ['chair', 'height', 'racket', 'touch', 'tunic']

def findChains(words):
    dictionary = defaultdict(list)
    
    for word in words:
        dictionary[word[0]].append(word)

    chains = [[words[0]]]  # start with an arbitrary word

    while True:
        new_chains = []

        for chain in chains:
            for follower in dictionary[chain[-1][-1]]:
                if follower in chain:
                    continue

                new_chains.append([*chain, follower])

        if new_chains:
            chains = new_chains
        else:
            break

    return [chain for chain in chains if len(chain) == len(words) and chain[-1][-1] == chain[0][0]]
        
print(findChains(words))

OUTPUT

% python3 test.py
[['chair', 'racket', 'touch', 'height', 'tunic']]
% 

Is the issue that a simple algorithm like the above becomes unworkable as the list of words gets longer? You also seem to assume a single solution, but with enough start and end letter redundancy, there could be multiple solutions. You need to code for multiple even if in the end you just pick one.