TADM2E 4.19 - Revision history

Matt: Undo revision 1081 by FuckMatt (talk)

2020-08-01T00:52:44Z

Undo revision 1081 by FuckMatt (talk)

FuckMatt: Redirected page to UNTV

2020-07-31T10:12:30Z

Redirected page to UNTV

Matt: Undo revision 956 by Erecua (talk)

2020-07-24T13:09:05Z

Undo revision 956 by Erecua (talk)

Erecua: Blanked the page

2020-07-24T12:06:13Z

Blanked the page

Cptsudoku: Formatting edit

2015-03-19T12:58:29Z

Formatting edit

Cptsudoku: Additional solution to assignment no. 3.

2015-03-19T12:57:11Z

Additional solution to assignment no. 3.

Algowikiadmin: Recovering wiki

2014-09-11T18:22:50Z

Recovering wiki

Algowikiadmin: Recovering wiki

2014-09-11T18:13:32Z

Recovering wiki

New page

1) Starting from left to right, the number of inversions
for 1st number is n-1
for 2nd number is n-2
...
..
....nth number is n-n = 0

Total number of inversions is the sum of all of the above
sum of integers from 0 to n - 1 = n(n-1)/2

2. We know that the maximum num of inversions is n(n-1)/2.
Consider a permutation P.
a1 a2 ai..ak...aj..am.... an-1 an

ai and aj are out of order
ak and am are in order.
For Pr,
ai and aj will get reversed, and will become in order.
ak and am will get reversed and will become out of order.

Every In order pair becomes an inversion.
And every inversion becomes corrected.

If P contains "x" inversions.. then it also contained "n(n-1)/2 - x" in order pairs.
Thus Pr contains "x" in order pairs and "n(n-1)/2 - x" inversions.

Summing up the inversions in P and Pr we get n(n-1)/2

3. To calculate the max inversions in part 1,
every ith position had n - i inversions.
i.e following a number, all other numbers will be out of order.
In the average case, we can argue that about 1/2 of the number will be
out of order....

for 1st number (n-1)/2
for 2nd number (n-2)/2
...
..
....nth number is (n-n)/2 = 0

Total number of inversions is the sum of all of the above
sum of integers from 0 to (n - 1)/2 = n(n-1)/4...

← Older revision		Revision as of 10:12, 31 July 2020
Line 1:		Line 1:
−	~~1) Starting from left to right, the number of inversions~~	+	#REDIRECT [[UNTV]]
−	~~for 1st number is n-1~~
−	~~for 2nd number is n-2~~
−	~~...~~
−	..
−	~~....nth number is n-n = 0~~
−
−	~~Total number of inversions is the sum of all of the above~~
−	~~sum of integers from 0 to n - 1 = n(n-1)/2~~
−
−	~~2. We know that the maximum num of inversions is n(n-1)/2.~~
−	~~Consider a permutation P.~~
−	~~a1 a2 ai..ak...aj..am.... an-1 an~~
−
−	~~ai and aj are out of order~~
−	~~ak and am are in order.~~
−	~~For Pr,~~
−	~~ai and aj will get reversed, and will become in order.~~
−	~~ak and am will get reversed and will become out of order.~~
−
−	~~Every In order pair becomes an inversion.~~
−	~~And every inversion becomes corrected.~~
−
−	~~If P contains "x" inversions.. then it also contained "n(n-1)/2 - x" in order pairs.~~
−	~~Thus Pr contains "x" in order pairs and "n(n-1)/2 - x" inversions.~~
−
−	~~Summing up the inversions in P and Pr we get n(n-1)/2~~
−
−	~~3. To calculate the max inversions in part 1,~~
−	~~every ith position had n - i inversions.~~
−	~~i.e following a number, all other numbers will be out of order.~~
−	~~In the average case, we can argue that about 1/2 of the number will be~~
−	~~out of order....~~
−
−	~~for 1st number (n-1)/2~~
−	~~for 2nd number (n-2)/2~~
−	~~...~~
−	..
−	~~....nth number is (n-n)/2 = 0~~
−
−	~~Total number of inversions is the sum of all of the above~~
−	~~sum of integers from 0 to (n - 1)/2 = n(n-1)/4...~~
−
−	'''Alternative solution to 3:''' Any permutation of any set is equally likely. Previous result shows that every permutation has its reversal. If we put pair up every permutation of a set with its reversal, they combine to n(n-1)/2 inversions. There are half as much pairs as there are permutations so the result is n(n-1)/2 * 1/2 = n(n-1)/4

← Older revision		Revision as of 12:06, 24 July 2020
Line 1:		Line 1:
−	~~1) Starting from left to right, the number of inversions~~
−	~~for 1st number is n-1~~
−	~~for 2nd number is n-2~~
−	~~...~~
−	..
−	~~....nth number is n-n = 0~~

−	~~Total number of inversions is the sum of all of the above~~
−	~~sum of integers from 0 to n - 1 = n(n-1)/2~~
−
−	~~2. We know that the maximum num of inversions is n(n-1)/2.~~
−	~~Consider a permutation P.~~
−	~~a1 a2 ai..ak...aj..am.... an-1 an~~
−
−	~~ai and aj are out of order~~
−	~~ak and am are in order.~~
−	~~For Pr,~~
−	~~ai and aj will get reversed, and will become in order.~~
−	~~ak and am will get reversed and will become out of order.~~
−
−	~~Every In order pair becomes an inversion.~~
−	~~And every inversion becomes corrected.~~
−
−	~~If P contains "x" inversions.. then it also contained "n(n-1)/2 - x" in order pairs.~~
−	~~Thus Pr contains "x" in order pairs and "n(n-1)/2 - x" inversions.~~
−
−	~~Summing up the inversions in P and Pr we get n(n-1)/2~~
−
−	~~3. To calculate the max inversions in part 1,~~
−	~~every ith position had n - i inversions.~~
−	~~i.e following a number, all other numbers will be out of order.~~
−	~~In the average case, we can argue that about 1/2 of the number will be~~
−	~~out of order....~~
−
−	~~for 1st number (n-1)/2~~
−	~~for 2nd number (n-2)/2~~
−	~~...~~
−	..
−	~~....nth number is (n-n)/2 = 0~~
−
−	~~Total number of inversions is the sum of all of the above~~
−	~~sum of integers from 0 to (n - 1)/2 = n(n-1)/4...~~
−
−	'''Alternative solution to 3:''' Any permutation of any set is equally likely. Previous result shows that every permutation has its reversal. If we put pair up every permutation of a set with its reversal, they combine to n(n-1)/2 inversions. There are half as much pairs as there are permutations so the result is n(n-1)/2 * 1/2 = n(n-1)/4

← Older revision		Revision as of 12:58, 19 March 2015
Line 42:		Line 42:
	sum of integers from 0 to (n - 1)/2 = n(n-1)/4...		sum of integers from 0 to (n - 1)/2 = n(n-1)/4...

−	Alternative solution: Any permutation of any set is equally likely. Previous result shows that every permutation has its reversal. If we put pair up every permutation of a set with its reversal, they combine to n(n-1)/2 inversions. There are half as much pairs as there are permutations so the result is n(n-1)/2 * 1/2 = n(n-1)/4	+	'''Alternative solution to 3:''' Any permutation of any set is equally likely. Previous result shows that every permutation has its reversal. If we put pair up every permutation of a set with its reversal, they combine to n(n-1)/2 inversions. There are half as much pairs as there are permutations so the result is n(n-1)/2 * 1/2 = n(n-1)/4

← Older revision		Revision as of 12:57, 19 March 2015
Line 41:		Line 41:
	Total number of inversions is the sum of all of the above		Total number of inversions is the sum of all of the above
	sum of integers from 0 to (n - 1)/2 = n(n-1)/4...		sum of integers from 0 to (n - 1)/2 = n(n-1)/4...
		+
		+	Alternative solution: Any permutation of any set is equally likely. Previous result shows that every permutation has its reversal. If we put pair up every permutation of a set with its reversal, they combine to n(n-1)/2 inversions. There are half as much pairs as there are permutations so the result is n(n-1)/2 * 1/2 = n(n-1)/4

← Older revision		Revision as of 00:52, 1 August 2020
Line 1:		Line 1:
−	~~#REDIRECT [[UNTV]]~~	+	1) Starting from left to right, the number of inversions
		+	for 1st number is n-1
		+	for 2nd number is n-2
		+	...
		+	..
		+	....nth number is n-n = 0
		+
		+	Total number of inversions is the sum of all of the above
		+	sum of integers from 0 to n - 1 = n(n-1)/2
		+
		+	2. We know that the maximum num of inversions is n(n-1)/2.
		+	Consider a permutation P.
		+	a1 a2 ai..ak...aj..am.... an-1 an
		+
		+	ai and aj are out of order
		+	ak and am are in order.
		+	For Pr,
		+	ai and aj will get reversed, and will become in order.
		+	ak and am will get reversed and will become out of order.
		+
		+	Every In order pair becomes an inversion.
		+	And every inversion becomes corrected.
		+
		+	If P contains "x" inversions.. then it also contained "n(n-1)/2 - x" in order pairs.
		+	Thus Pr contains "x" in order pairs and "n(n-1)/2 - x" inversions.
		+
		+	Summing up the inversions in P and Pr we get n(n-1)/2
		+
		+	3. To calculate the max inversions in part 1,
		+	every ith position had n - i inversions.
		+	i.e following a number, all other numbers will be out of order.
		+	In the average case, we can argue that about 1/2 of the number will be
		+	out of order....
		+
		+	for 1st number (n-1)/2
		+	for 2nd number (n-2)/2
		+	...
		+	..
		+	....nth number is (n-n)/2 = 0
		+
		+	Total number of inversions is the sum of all of the above
		+	sum of integers from 0 to (n - 1)/2 = n(n-1)/4...
		+
		+	'''Alternative solution to 3:''' Any permutation of any set is equally likely. Previous result shows that every permutation has its reversal. If we put pair up every permutation of a set with its reversal, they combine to n(n-1)/2 inversions. There are half as much pairs as there are permutations so the result is n(n-1)/2 * 1/2 = n(n-1)/4

← Older revision	Revision as of 13:09, 24 July 2020
Line 1:	Line 1:
	+	1) Starting from left to right, the number of inversions
	+	for 1st number is n-1
	+	for 2nd number is n-2
	+	...
	+	..
	+	....nth number is n-n = 0

	+	Total number of inversions is the sum of all of the above
	+	sum of integers from 0 to n - 1 = n(n-1)/2
	+
	+	2. We know that the maximum num of inversions is n(n-1)/2.
	+	Consider a permutation P.
	+	a1 a2 ai..ak...aj..am.... an-1 an
	+
	+	ai and aj are out of order
	+	ak and am are in order.
	+	For Pr,
	+	ai and aj will get reversed, and will become in order.
	+	ak and am will get reversed and will become out of order.
	+
	+	Every In order pair becomes an inversion.
	+	And every inversion becomes corrected.
	+
	+	If P contains "x" inversions.. then it also contained "n(n-1)/2 - x" in order pairs.
	+	Thus Pr contains "x" in order pairs and "n(n-1)/2 - x" inversions.
	+
	+	Summing up the inversions in P and Pr we get n(n-1)/2
	+
	+	3. To calculate the max inversions in part 1,
	+	every ith position had n - i inversions.
	+	i.e following a number, all other numbers will be out of order.
	+	In the average case, we can argue that about 1/2 of the number will be
	+	out of order....
	+
	+	for 1st number (n-1)/2
	+	for 2nd number (n-2)/2
	+	...
	+	..
	+	....nth number is (n-n)/2 = 0
	+
	+	Total number of inversions is the sum of all of the above
	+	sum of integers from 0 to (n - 1)/2 = n(n-1)/4...
	+
	+	'''Alternative solution to 3:''' Any permutation of any set is equally likely. Previous result shows that every permutation has its reversal. If we put pair up every permutation of a set with its reversal, they combine to n(n-1)/2 inversions. There are half as much pairs as there are permutations so the result is n(n-1)/2 * 1/2 = n(n-1)/4

@@ Line 22: / Line 22: @@
    And every inversion becomes corrected.
-If P contains &quot;x&quot; inversions.. then it also contained &quot;n(n-1)/2 - x&quot; in order pairs.
+If P contains "x" inversions.. then it also contained "n(n-1)/2 - x" in order pairs.
-Thus Pr contains &quot;x&quot; in order pairs and &quot;n(n-1)/2 - x&quot; inversions.
+Thus Pr contains "x" in order pairs and "n(n-1)/2 - x" inversions.
 Summing up the inversions in P and Pr we get n(n-1)/2