The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+3 votes

No of topological sortings

asked in Algorithms by Active (1.6k points)
retagged by | 476 views
There is no confusion in B->D->F

everything lies on A,C,E

I made some initial mistakes!!!

so considered ACE, but not ECA like possibilities

now 15 coming

i am getting 15

corret me if i am wrong
I am getting 15 ??
me too getting 15
i am also getting 15

Im getting 6 only !
Where am I doing wrong ?

Start with "A"

  • A-B-D-F-C-E
  • A-B-D-F-E-C

Start with "C"

  • C-D-F-E-A-B
  • C-D-F-A-B-E

Start with "E"

  • E-F-A-B-D-C
  • E-F-C-D-A-B
There are $8$ possibilities starting with $A$.
You are missing ::
(starting with A)
A-B-E-C-D-F + many more

Starting with A = 8, with C = 4, with E = 3 $\Rightarrow $ Total = $15$
And E-F-A-B-D-C is not a topological sort.
Any good resouces to learn this topic ?
  1. draw the graph
  2. See How many vertices have in-degree $0$
  3. start with any vertex with in-degree $0$,note it down.
  4. Remove that vertex and associated edges
  5. Next see how many vertices now with in-degree $0$ after removal of that vertex and associated edeges.
  6. Go to step 3 and repeat till the end of all vertices.

While performing these steps we have to consider all available options . 

Thank you so much :)
is there any efficient way using combinatorics? i solved it and it took around 4 min. for me to get the answer. i don't want it to happen in exam.

3 Answers

+2 votes
A -> B -> D -> F sequence is fixed .now C can be anywere before D.and E can be anywhere after F
So, C can be at any of 3 place (shown with " _ " )

 _A_B_D ->F
take case 1: C at first position CABDF now Ecan be at

_C_A_B_D_ ->F at 5 places
similarly for remaining 2 cases as

_A_C_B_D_ ->F and 5 places

  _A_B_C_D_ ->F 5 places

total 15 no. of topological sorting sequence
answered by Loyal (7.6k points)
edited by
now C can be anywere after D, it is not after, it should be "before" I guess.
Yup.. Editing..
0 votes
Please check:

ABDF are fixed. Remaining 2 are to be placed: _A_B_D_F_

Nothing comes after F, and E<F and C<D

=> _A_B_D_F

If E comes before 4th dash: 1st, 2nd, 3rd dash: Each has 2 choices => 8 ways

If E comes at 4th dash, 1st,2nd,3rd dash have 1 choice each => 3*1*1 = 3 ways

Ans = 8+3= 11
answered by Active (1.6k points)

C comes at 1st position ->3 ways to choose for E between 2,3,4

C comes at 2nd pposition ->3 ways to chosse for E between 1,3,4

C comes at 3rd position -> 3 ways to choose for E between 1,2,4

Total = 9
0 votes
I am also getting 15.
answered by (89 points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,162 questions
44,732 answers
43,805 users