Difference between revisions of "Talk:TADM2E 3.28"

From Algorithm Wiki
Jump to: navigation, search
(I don't think the solution is on this wiki yet.)
m (Use colspan)
 
(2 intermediate revisions by the same user not shown)
Line 19: Line 19:
  
  
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)
+
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
 +
|-
 +
|colspan="5"| Forwards:
 +
|-
 +
|
 +
| '''a'''
 +
|
 +
|
 +
|
 +
|-
 +
|
 +
| a
 +
| '''ab'''
 +
|
 +
|
 +
|-
 +
|
 +
| a
 +
| ab
 +
| '''abc'''
 +
|
 +
|-
 +
|
 +
| a
 +
| ab
 +
| abc
 +
| '''abcd'''
 +
|-
 +
|colspan="5"| 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)

Latest revision as of 12:30, 8 November 2015

I think this can be done in a single loop essentially taking two passes at once. Here is a Python snippet.

# 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


Note by murrayc:

I think this should be the main solution, and I think this helps to visualise what is happening:

--Murrayc2 (talk) 07:29, 8 November 2015 (EST)
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