Non-Adjacent Combinations of Two Words
Given a sentence as input, find all the unique combinations of two words and print the word combinations that are not adjacent in the original sentence in lexicographical order.
Input
The input will be a single line containing a sentence.
Output
The output should be multiple lines, each line containing a valid unique combination of two words. The words in each line should be lexicographical order and the lines as well should be in lexicographical order. A valid combination will not contain the words that appear adjacent in the given sentence. Print "No Combinations" if there are no valid combinations.
Sample Input 1
raju always plays cricket
Sample Output 1
always cricket
cricket raju
plays raju
Sample Input 2
python is a programming language
Sample Output 2
a language
a python
is language
is programming
language python
programming python
Sample Input 3
to be or not to be
Sample Output 3
be be
be not
or to
to to
In this python code there are three test cases. The three test cases are not coming expected output.
The three test cases are below.
sentence = "to be or not to be"
s = sentence.split[]
s.sort[]
result = []
for word1 in s:
for word2 in s:
result.append[word1 + " " + word2]
result = set[result]
result = list[result]
result.sort[]
for item in result:
if item in sentence:
result.remove[item]
for item in result:
if " ".join[item.split[][::-1]] in sentence:
result.remove[item]
for item in result:
spl = item.split[]
if [spl[0] == spl[1]] and [sentence.count[spl[0]] < 2]:
result.remove[item]
for item in result:
spl = item.split[]
dup = spl[1] + " " + spl[0]
if dup in result:
result.remove[dup]
result.insert[0, "be be"]
for item in result:
print[item]
Test cases
Test case 1
Input:-
raju always plays cricket
Output:-
Expected output is
always cricket
cricket raju
plays raju
but coming output is
be be
not be
or be
or to
Test case 2
Input:-
python is a programming language
Output:-
Expected output is
a language
a python
is language
is programming
language python
programming python
but coming output is
be be
not be
or be
or to
Test case 3
Input:-
to be or not to be
Output:-
Expected output is
be be
be not
or to
to to
but coming output is
be be
not be
or be
or to
Python provides direct methods to find permutations and combinations of a sequence. These methods are present in itertools package.
Permutation
First import itertools package to implement the permutations method in python. This method takes a list as an input and returns an object list of tuples that contain all permutations in a list form.
Python3
from
itertools
import
permutations
perm
=
permutations[[
1
,
2
,
3
]]
for
i
in
list
[perm]:
print
[i]
Output:
[1, 2, 3] [1, 3, 2] [2, 1, 3] [2, 3, 1] [3, 1, 2] [3, 2, 1]
It generates n! permutations if the length of the input sequence is n.
If want to get permutations of length L then implement it in this way.
Python3
from
itertools
import
permutations
perm
=
permutations[[
1
,
2
,
3
],
2
]
for
i
in
list
[perm]:
print
[i]
Output:
[1, 2] [1, 3] [2, 1] [2, 3] [3, 1] [3, 2]
It generates nCr * r! permutations if the length of the input sequence is n and the input parameter is r.
Combination
This method takes a list and an input r as an input and return an object list of tuples which contain all possible combination of
length r in a list form.
Python3
from
itertools
import
combinations
comb
=
combinations[[
1
,
2
,
3
],
2
]
for
i
in
list
[comb]:
print
[i]
Output:
[1, 2] [1, 3] [2, 3]
1. Combinations are emitted in lexicographic sort order of input. So, if the input list is sorted, the combination tuples will be
produced in sorted order.
Python3
from
itertools
import
combinations
comb
=
combinations[[
1
,
2
,
3
],
2
]
for
i
in
list
[comb]:
print
[i]
Output:
[1, 2] [1, 3] [2, 3]
2. Elements are treated as unique based on their position, not on their value. So if the input elements are unique, there will
be no repeat values in each combination.
Python3
from
itertools
import
combinations
comb
=
combinations[[
2
,
1
,
3
],
2
]
for
i
in
list
[comb]:
print
[i]
Output:
[2, 1] [2, 3] [1, 3]
3. If we want to make a combination of the same element to the same element then we use
combinations_with_replacement.
Python3
from
itertools
import
combinations_with_replacement
comb
=
combinations_with_replacement[[
1
,
2
,
3
],
2
]
for
i
in
list
[comb]:
print
[i]
Output:
[1, 1] [1, 2] [1, 3] [2, 2] [2, 3] [3, 3]