Order of teams in a tournament such that every team has won against its consecutive team
Given N teams and the results of round-robin tournament in which no match resulted is draw or tie. The task is to find the order of the teams such that every team has won against its consecutive team. Examples:
Input: N = 4 results[] = {{1, 4}, {4, 3}, {2, 3}, {1, 2}, {2, 1}, {3, 1}, {2, 4}}
Output: 2 4 3 1
Explanation: Team-2 has won against Team-4, in the last match. Team-3 has lost to Team-4 in the 2nd match and Team-3 won against Team-1 in the second last match. Therefore, every team has won against the team next to itself.Input: N = 5 results[] = {{1, 4}, {4, 3}, {2, 3}, {1, 2}, {2, 1}, {3, 1}, {4, 2}, {2, 5}, {5, 3}, {4, 5}, {5, 1}}
Output: 4 2 5 3 1
Approach: The idea is to maintain a hash-map for every team which stores the teams against which the team has won in the round-robin tournament. This can be done by iterating over the elements of the results and for each winner append it to the list of the hash-map object of that team.
The hashtable for an example is as follows: Key Value Team-1 => [Team-4, Team-2] Team-2 => [Team-3, Team-1, Team-4] Team-3 => [Team-1] Team-4 => [Team-3]
Finally, compute the order of teams using recursively. Below is the illustration of the recursive function:
- Base Case: When the current length of the teams is 1, return the team.
- Recursive Case: Compute the order of the N – 1 team and after the computation of the teams, Iterate over the order of the teams and find a position where the current team has lost against its previous team. If there is no such position append the team at the last position.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h> using namespace std; class Result { public : int winner; int loser; Result( int winner, int loser) { this ->winner = winner; this ->loser = loser; } }; void SetInOrder(vector< int > teams, map< int , vector< int >> mp, int n, vector< int >& output) { if (n < 1) { return ; } else if (n == 1) { output.push_back(teams[n - 1]); return ; } SetInOrder(teams, mp, n - 1, output); int key = teams[n - 1]; int i; for (i = 0; i < output.size(); i++) { int team = output[i]; vector< int > losers = mp[key]; if (find(losers.begin(), losers.end(), team) != losers.end()) { break ; } } output.insert(output.begin() + i, key); } void ArrangeTeams(vector< int > teams, vector<Result> results) { map< int , vector< int >> mp; int winner = 0; for ( int i = 0; i < results.size(); i++) { winner = results[i].winner; if (mp.find(winner) != mp.end()) { mp[winner].push_back(results[i].loser); } else { mp[winner] = {results[i].loser}; } } vector< int > output; SetInOrder(teams, mp, teams.size(), output); for ( int i = 0; i < output.size(); i++) { cout << output[i] << " " ; } } int main() { vector< int > teams = {1, 2, 3, 4}; vector<Result> results = {Result(1, 4), Result(4, 3), Result(2, 3), Result(1, 2), Result(2, 1), Result(3, 1), Result(2, 4)}; ArrangeTeams(teams, results); return 0; } |
Java
// Java implementation to find the // order of the teams in a round // robin tournament such that every // team has won against to its next team import java.util.*; import java.lang.*; // A class to represent result // of a match of a tournament. class Result { int winner; int loser; Result( int winner, int loser) { this .winner = winner; this .loser = loser; } } public class TeamOrdering { // Function to arrange the teams of // the round-robin tournament static void arrangeTeams( int [] teams, Result[] results) { HashMap<Integer, List<Integer> > map = new HashMap<>(); int winner = 0 ; // Creating a hashmap of teams // and the opponents against // which they have won, using // the results of the tournament for ( int i = 0 ; i < results.length; i++) { winner = results[i].winner; if (map.containsKey(winner)) { map.get(winner).add( results[i].loser); } else { List<Integer> list = new ArrayList<Integer>(); list.add(results[i].loser); map.put(winner, list); } } List<Integer> output = new ArrayList<>(); // Arrange the teams in required order setInOrder(teams, map, teams.length, output); Iterator<Integer> it = output.iterator(); // Displaying the final output while (it.hasNext()) { System.out.print(it.next()); System.out.print( " " ); } } // Function to determine // the order of teams static void setInOrder( int [] teams, HashMap<Integer, List<Integer> > map, int n, List<Integer> output) { // Base Cases if (n < 1 ) { return ; } // If there is only 1 team, // add it to the output else if (n == 1 ) { output.add(teams[n - 1 ]); return ; } // Recursive call to generate // output for N-1 teams setInOrder(teams, map, n - 1 , output); int key = teams[n - 1 ]; int i; // Finding the position for the // current team in the output list. for (i = 0 ; i < output.size(); i++) { // Obtain the team at current // index in the list int team = output.get(i); // Check if it has lost against // current team List<Integer> losers = map.get(key); if (losers.indexOf(team) != - 1 ) break ; } // Add the current team // to its final position output.add(i, key); } // Driver Code public static void main(String[] args) { int [] teams = { 1 , 2 , 3 , 4 }; Result[] results = { new Result( 1 , 4 ), new Result( 4 , 3 ), new Result( 2 , 3 ), new Result( 1 , 2 ), new Result( 2 , 1 ), new Result( 3 , 1 ), new Result( 2 , 4 ) }; // Function Call arrangeTeams(teams, results); } } |
Python3
# Python implementation to find the # order of the teams in a round # robin tournament such that every # team has won against to its next team from typing import List import collections # A class to represent result # of a match of a tournament. class Result: def __init__( self , winner, loser): self .winner = winner self .loser = loser # Function to arrange the teams of # the round-robin tournament def arrange_teams(teams: List [ int ], results: List [Result]) - > List [ int ]: map = collections.defaultdict( list ) winner = 0 # Creating a dictionary of teams # and the opponents against # which they have won, using # the results of the tournament for i in range ( len (results)): winner = results[i].winner map [winner].append(results[i].loser) output = [] # Arrange the teams in required order set_in_order(teams, map , len (teams), output) return output # Function to determine # the order of teams def set_in_order( teams: List [ int ], map : dict , n: int , output: List [ int ] ) - > None : # Base Cases if n < 1 : return # If there is only 1 team, # add it to the output elif n = = 1 : output.append(teams[n - 1 ]) return # Recursive call to generate # output for N-1 teams set_in_order(teams, map , n - 1 , output) key = teams[n - 1 ] i = 0 # Finding the position for the # current team in the output list. for i in range ( len (output)): # Obtain the team at current # index in the list team = output[i] # Check if it has lost against # current team losers = map .get(key, []) if team in losers: break # Add the current team # to its final position output.insert(i, key) # Driver Code if __name__ = = '__main__' : teams = [ 1 , 2 , 3 , 4 ] results = [ Result( 1 , 4 ), Result( 4 , 3 ), Result( 2 , 3 ), Result( 1 , 2 ), Result( 2 , 1 ), Result( 3 , 1 ), Result( 2 , 4 ) ] # Function Call output = arrange_teams(teams, results) print (output) |
C#
// C# program for the above approach using System; using System.Collections.Generic; public class Result { public int winner; public int loser; public Result( int winner, int loser) { this .winner = winner; this .loser = loser; } } public class TeamOrdering { // Driver Code static void Main( string [] args) { int [] teams = { 1, 2, 3, 4 }; Result[] results = { new Result(1, 4), new Result(4, 3), new Result(2, 3), new Result(1, 2), new Result(2, 1), new Result(3, 1), new Result(2, 4) }; // Function Call ArrangeTeams(teams, results); } // Function to arrange the teams of // the round-robin tournament static void ArrangeTeams( int [] teams, Result[] results) { Dictionary< int , List< int > > map = new Dictionary< int , List< int > >(); int winner = 0; // Creating a dictionary of teams // and the opponents against // which they have won, using // the results of the tournament for ( int i = 0; i < results.Length; i++) { winner = results[i].winner; if (map.ContainsKey(winner)) { map[winner].Add(results[i].loser); } else { List< int > list = new List< int >(); list.Add(results[i].loser); map.Add(winner, list); } } List< int > output = new List< int >(); // Arrange the teams in required order SetInOrder(teams, map, teams.Length, output); foreach ( int item in output) { Console.Write(item + " " ); } } // Function to determine // the order of teams static void SetInOrder( int [] teams, Dictionary< int , List< int > > map, int n, List< int > output) { // Base Cases if (n < 1) { return ; } // If there is only 1 team, // add it to the output else if (n == 1) { output.Add(teams[n - 1]); return ; } // Recursive call to generate // output for N-1 teams SetInOrder(teams, map, n - 1, output); int key = teams[n - 1]; int i; // Finding the position for the // current team in the output list. for (i = 0; i < output.Count; i++) { // Obtain the team at current // index in the list int team = output[i]; // Check if it has lost against // current team List< int > losers = map[key]; if (losers.IndexOf(team) != -1) break ; } // Add the current team // to its final position output.Insert(i, key); } } // This code is contributed by codebraxnzt |
Javascript
// JavaScript Program for the above approach class Result { constructor(winner, loser) { this .winner = winner; this .loser = loser; } } function ArrangeTeams(teams, results) { let map = new Map(); let winner = 0; for (let i = 0; i < results.length; i++) { winner = results[i].winner; if (map.has(winner)) { map.get(winner).push(results[i].loser); } else { map.set(winner, [results[i].loser]); } } let output = []; SetInOrder(teams, map, teams.length, output); console.log(output.join( ' ' )); } function SetInOrder(teams, map, n, output) { if (n < 1) { return ; } else if (n === 1) { output.push(teams[n - 1]); return ; } SetInOrder(teams, map, n - 1, output); let key = teams[n - 1]; let i; for (i = 0; i < output.length; i++) { let team = output[i]; let losers = map.get(key); if (losers.indexOf(team) !== -1) { break ; } } output.splice(i, 0, key); } let teams = [1, 2, 3, 4]; let results = [ new Result(1, 4), new Result(4, 3), new Result(2, 3), new Result(1, 2), new Result(2, 1), new Result(3, 1), new Result(2, 4)]; ArrangeTeams(teams, results); // This code is contributed by adityashatmfh |
2 4 3 1
Performance Analysis:
- Time Complexity: O(N2)
- Auxiliary Space: O(N)
Contact Us