Talk:TADM2E 3.28 - Revision history

Murrayc2: Use colspan

2015-11-08T12:30:38Z

Use colspan

Murrayc2 at 12:29, 8 November 2015

2015-11-08T12:29:18Z

Murrayc2: This actually seems to be doing 4 multiplications n times, so it is O(n).

2015-11-08T11:34:00Z

This actually seems to be doing 4 multiplications n times, so it is O(n).

Murrayc2: I don't think the solution is on this wiki yet.

2015-11-08T11:17:17Z

I don't think the solution is on this wiki yet.

Brownslink: Single Pass in Python

2015-02-02T12:09:56Z

Single Pass in Python

Brownslink: Perform in single pass

2015-02-02T12:00:20Z

Perform in single pass

New page

I think this can be done in a single loop essentially taking two passes at once. Here is a Python snippet.
<nowiki>
# O( n) - len( input_values)
length = len( input_values) # the length of the input values
answers = [1]*length # output values
frontIndex = 0 # the index at which we have calculated the product of all preceding indexes
frontProduct = 1 # the product of values preceding the front index
backProduct = 1 # the product of values following the back index
limit = length-1
backIndex = limit # the index at which we have calculated the product of all following values
while( frontIndex < limit):
frontProduct *= input_values[ frontIndex]
backProduct *= input_values[ backIndex]
frontIndex += 1
answers[ frontIndex] *= frontProduct
backIndex -= 1
answers[ backIndex] *= backProduct
</nowiki>

@@ Line 30: / Line 30: @@
 ! e
 |-
-| Forwards:
+|colspan="5"| Forwards:
 |-
+|
@@ Line 56: / Line 56: @@
 | '''abcd'''
 |-
-| Backwards:
+|colspan="5"| Backwards:
 |-
+|

← Older revision		Revision as of 12:29, 8 November 2015
Line 17:		Line 17:
	answers[ backIndex] *= backProduct		answers[ backIndex] *= backProduct
	</source>		</source>
		+
		+
		+	Note by murrayc:
		+
		+	I think this should be the main solution, and I think this helps to visualise what is happening:
		+
		+	{\| class="wikitable" \|
		+	! a
		+	! b
		+	! c
		+	! d
		+	! e
		+	\|-
		+	\| Forwards:
		+	\|-
		+	\|
		+	\| '''a'''
		+	\|
		+	\|
		+	\|
		+	\|-
		+	\|
		+	\| a
		+	\| '''ab'''
		+	\|
		+	\|
		+	\|-
		+	\|
		+	\| a
		+	\| ab
		+	\| '''abc'''
		+	\|
		+	\|-
		+	\|
		+	\| a
		+	\| ab
		+	\| abc
		+	\| '''abcd'''
		+	\|-
		+	\| Backwards:
		+	\|-
		+	\|
		+	\| a
		+	\| ab
		+	\| (abc) '''(e)'''
		+	\| abcd
		+	\|-
		+	\|
		+	\| a
		+	\| (ab) '''(ed)'''
		+	\| (abc) (e)
		+	\| abcd
		+	\|-
		+	\|
		+	\| (a) '''(edc)'''
		+	\| (ab) (ed)
		+	\| (abc) (e)
		+	\| abcd
		+	\|-
		+	\| '''(edcb)'''
		+	\| (a) (edc)
		+	\| (ab) (ed)
		+	\| (abc) (e)
		+	\| abcd
		+	\|-\|}
		+
		+	--[[User:Murrayc2\|Murrayc2]] ([[User talk:Murrayc2\|talk]]) 07:29, 8 November 2015 (EST)

← Older revision		Revision as of 11:34, 8 November 2015
Line 17:		Line 17:
	answers[ backIndex] *= backProduct		answers[ backIndex] *= backProduct
	</source>		</source>
−
−
−	Both this suggestion and the solution given on the page still seem to be doing n-1 multiplications on n items, so they still seem to be n^2. --[[User:Murrayc2\|Murrayc2]] ([[User talk:Murrayc2\|talk]]) 06:17, 8 November 2015 (EST)

← Older revision		Revision as of 11:17, 8 November 2015
Line 17:		Line 17:
	answers[ backIndex] *= backProduct		answers[ backIndex] *= backProduct
	</source>		</source>
		+
		+
		+	Both this suggestion and the solution given on the page still seem to be doing n-1 multiplications on n items, so they still seem to be n^2. --[[User:Murrayc2\|Murrayc2]] ([[User talk:Murrayc2\|talk]]) 06:17, 8 November 2015 (EST)

@@ Line 1: / Line 1: @@
 I think this can be done in a single loop essentially taking two passes at once.  Here is a Python snippet.
-  <nowiki>
+  <source lang="Python">
 # O( n) - len( input_values)
 length = len( input_values)		# the length of the input values
@@ Line 16: / Line 16: @@
      backIndex -= 1
      answers[ backIndex] *= backProduct
-  </nowiki>
+  </source>